Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in C++

BinaryTree: A Basic Binary Tree

Explore the fundamental concepts of binary trees, including node representation, recursive and non-recursive traversal methods, and computations of size and height. This lesson helps you understand how to build and manipulate binary trees in C++ with examples of node connections, traversals, and measuring tree properties to enhance your knowledge of tree data structures.

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:

C++
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:

C++
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:

C++
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:

C++
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:

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

Traversing binary trees

...