Data Structures with Generic Types in Java/

...

/

BinaryTree: A Basic Binary Tree

BinaryTree: A Basic Binary Tree

Learn BinaryTree implementation.

We'll cover the following...

The simplest way to represent a node, u, in a binary tree is to explicitly store the (at most three) neighbours of u:

Java
class BTNode < Node extends BTNode < Node >> {
  Node left;
  Node right;
  Node parent;
}

When one of these three neighbours is not present, we set it to nil. In this way, both external nodes of the tree and the parent of the root correspond to the value nil.

The binary tree itself can then be represented by a reference to its root node, r:

Java
Node r;

We can compute the depth of a node, u, in a binary tree by counting the number of steps on the path from u to the root:

Java
int depth(Node u) {
  int d = 0;
  while (u != r) {
    u = u.parent;
    d++;
  }
  return d;
}

Recursive algorithms

Using recursive algorithms makes it very easy to compute facts about binary trees. For example, to compute the size of (number of nodes in) a binary tree rooted at node u, we recursively compute the sizes of the two subtrees rooted at the children of u, sum up these sizes, and add one:

Java
int size(Node u) {
  if (u == nil) return 0;
  return 1 + size(u.left) + size(u.right);
}

To compute the height of a node u, we can compute the height of u’s two subtrees, take the maximum, and add one:

Java
int height(Node u) {
  if (u == nil) return -1;
  return 1 + max(height(u.left), height(u.right));
}

Traversing binary trees

The two ...