Data Structures with Generic Types in C++/

...

/

BinaryTree: A Basic Binary Tree

BinaryTree: A Basic Binary Tree

Learn about 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:

Press + to interact
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:

Press + to interact
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:

Press + to interact
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:

Press + to interact
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: ...

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy