Binary tree basics

Prerequisites

• Recursion: a function that calls itself on a smaller input.
• Structs and pointers in C.
• Linked lists: a tree node is a list node with two "next" pointers.

The analogy

How it works

Start with a small tree on paper

The tree is: root 1; children of 1 are 2 (left) and 3 (right); children of 2 are 4 and 5. Predict, then open "Check".

Finish the picture: the other traversals

Use the original tree (1; 2, 3; 4, 5 under 2).

• Pre-order (node, left, right). Predict the sequence.
  Check

  1, 2, 4, 5, 3.

• Post-order (left, right, node) and level order (row by row). Predict both.
  Check

  Post-order: 4, 5, 2, 3, 1. Level order: 1, 2, 3, 4, 5.

The rule in plain words

A binary tree is either empty, or a node with a value, a left subtree and a right subtree, each of which is a binary tree.

Almost every tree algorithm follows that definition: handle the empty tree, recurse on the two subtrees, and combine the results at the node.

The code

Read this code after you have done the traversal by hand. It will make more sense.

typedef struct Node { int val; struct Node *left, *right; } Node;

int height(Node *t) {                  /* edges on the longest root-to-leaf path */
    if (t == NULL) return -1;          /* empty tree */
    int l = height(t->left), r = height(t->right);
    return 1 + (l > r ? l : r);
}

int inorder(Node *t, int out[], int k) {   /* writes values into out, returns new k */
    if (t == NULL) return k;
    k = inorder(t->left, out, k);          /* left subtree first */
    out[k++] = t->val;                     /* then the node */
    return inorder(t->right, out, k);      /* then the right subtree */
}

graph TD
  A((1)) --> B((2))
  A --> C((3))
  B --> D((4))
  B --> E((5))
          

How fast is it?

Level $d$ holds at most $2^d$ nodes, so a tree of height $h$ holds at most:

So the best possible height is about $\log_2 n$, and the worst (every node with one child) is $n - 1$. Every traversal visits each node once: $O(n)$.

Common mistakes

• Mixing up in-order and pre-order: in-order visits the node between its subtrees.
• Returning 0 instead of −1 for an empty tree, which makes every height one too big under the edge convention.
• Forgetting the empty-tree base case, which dereferences NULL.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• Tree algorithms are recursive because a tree is a node plus two smaller trees.
• Traversals are $O(n)$ because each node is visited exactly once.
• A tree of $n$ nodes has height at least $\lfloor \log_2 n \rfloor$ because level $d$ can hold at most $2^d$ nodes.
• In-order puts the node in the middle because it finishes the left subtree before the node and the right subtree after.
• Recursion depth equals the height because each call goes one level down.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is a binary tree like an upside-down family tree?
   Sample answer

   One ancestor at the top (the root), each person with up to two children below, and people without children are the leaves.

2. Give the leaves, the height and the in-order traversal of the tree 1; 2, 3; 4, 5 under 2.
   Sample answer

   Leaves 4, 5, 3; height 2; in-order 4, 2, 5, 1, 3.

3. Why does height return −1 for an empty tree?

   A good answer checks a single node.

   Sample answer

   A single node should have height 0 edges. With −1 for empty children, it gets 1 + max(−1, −1) = 0, which is right.

4. So what is a binary tree, in one sentence?
   Sample answer

   A collection of nodes where each node has at most a left and a right child, starting from one root.

5. What are the four standard traversals, and how do they differ?
   Sample answer

   Pre-order visits the node before its subtrees, in-order between them, post-order after them, and level order goes row by row from the root.

6. Why is the best possible height about $\log_2 n$?

   A good answer counts nodes per level.

   Sample answer

   Each level can at most double the number of nodes, so $n$ nodes need at least about $\log_2 n$ levels.

7. What do traversals, height and search cost on a general binary tree?
   Sample answer

   All $O(n)$: each needs to look at every node in the worst case.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the height conventions and rebuilding from two traversals. I'd keep the family-tree analogy, the 5-node example with its traversals, and "recursion: node plus two subtrees".

External resources

• VisuAlgo: Binary trees: animate pre-, in- and post-order traversals.
• GeeksforGeeks: Binary tree: terminology, types and traversal code.
• Wikipedia: Binary tree: definitions, properties and counting formulas.

Videos

• YouTube search: tree traversals: pick a walkthrough of all three depth-first orders.