Trees and traversal

Start here: what this lesson is for

Trees are where recursion stops being an exercise and becomes the only sane way to write the code. If chapter 3 felt like homework, this is the lesson where it pays for itself.

The structure itself is a tiny change from what you already know: take chapter 6's node and give it two next references instead of one. Everything in this chapter follows from that.

What you gain is the halving from chapter 5, applied to data that changes. A sorted array gives fast search but slow insertion; a balanced tree gives both - and understanding why is the point of the next lesson.

A linked list that branches

Take chapter 6's node and give it two next references instead of one. That's a binary tree. Everything else in this chapter is a consequence of that single change.

The vocabulary is borrowed from family trees and drawn upside down: the root sits at the top, each node's references point to its children, a node with no children is a leaf, and the height is the longest path from root to leaf.

Branching changes the shape of the cost. Walking a linked list of n nodes takes n steps because there's one path. In a balanced tree, each step down halves what's left - so reaching any node takes about log n steps, the same halving you've seen in binary search and merge sort. Trees are how you get that halving on data that changes.

Three orders, one line moved

To do anything with a tree you must visit every node, and because a node has two children there is a genuine choice about when to handle the node itself: before its children, between them, or after both.

Those three choices are pre-order, in-order and post-order. The remarkable part is that the code is identical apart from where one line sits - and yet each order is the right tool for a different job.

Pre-order handles a node before descending, so it's how you copy or serialise a tree: the parent exists before its children need attaching. Post-order handles children first, so it's how you delete a tree or compute anything that depends on subtree results - heights, sums, sizes. In-order is the one with a special property, and the next lesson is built on it.

class Node { int value; Node left, right; }

void preOrder(Node n) {
    if (n == null) return;
    visit(n);              // <- before the children: parent exists first
    preOrder(n.left);
    preOrder(n.right);
}

void inOrder(Node n) {
    if (n == null) return;
    inOrder(n.left);
    visit(n);              // <- between them
    inOrder(n.right);
}

void postOrder(Node n) {
    if (n == null) return;
    postOrder(n.left);
    postOrder(n.right);
    visit(n);              // <- after both: children are done
}

4
       / \
      2   6
     / \ / \
    1  3 5  7

pre    4 2 1 3 6 5 7      (root first - copy/serialise)
in     1 2 3 4 5 6 7      (sorted! - see the next lesson)
post   1 3 2 5 7 6 4      (children first - delete/compute)

Going wide instead of deep

All three orders above dive as deep as they can before backing up - they are depth-first, and recursion gives you that for free because the call stack is doing the remembering.

Sometimes you want the opposite: visit everything one level at a time. That's breadth-first, and recursion cannot express it, because the call stack is a stack and you need a queue.

Which is chapter 7's punchline arriving early. Swap the container and the traversal's whole character changes: a stack dives, a queue fans out. Level-order answers questions depth-first traversals are clumsy at - the shallowest match, distance from the root, printing a tree by rows.

List<List<Integer>> levelOrder(Node root) {
    List<List<Integer>> levels = new ArrayList<>();
    if (root == null) return levels;

    Queue<Node> q = new ArrayDeque<>();
    q.add(root);
    while (!q.isEmpty()) {
        int levelSize = q.size();          // snapshot: today's row only
        List<Integer> row = new ArrayList<>();
        for (int i = 0; i < levelSize; i++) {
            Node n = q.poll();
            row.add(n.value);
            if (n.left != null)  q.add(n.left);
            if (n.right != null) q.add(n.right);
        }
        levels.add(row);
    }
    return levels;
}

[[4], [2, 6], [1, 3, 5, 7]]

queue: [4]           -> row [4],       enqueue 2,6
queue: [2,6]         -> row [2,6],     enqueue 1,3,5,7
queue: [1,3,5,7]     -> row [1,3,5,7]

Height, depth, and why balance decides everything

Two words get confused constantly, so pin them down now. The depth of a node is how far it sits below the root. The height of a tree is the depth of its deepest node - the length of the longest root-to-leaf path.

Height is the number that matters, because almost every tree operation walks one root-to-leaf path. Search, insert and delete are all O(height), not O(n).

That is only good news if the height is small. A balanced tree of n nodes has height around log2(n): a million nodes in twenty levels. A degenerate one - every node with a single child - has height n, and every operation becomes a linear walk.

So 'trees are O(log n)' is a statement about balance, not about trees. The next lesson shows exactly how a binary search tree degenerates, and it happens on the most ordinary input imaginable.

int height(Node n) {
    if (n == null) return 0;                         // empty tree
    return 1 + Math.max(height(n.left), height(n.right));
}

BALANCED, 7 nodes            DEGENERATE, 7 nodes
        4                          1
      /   \                          \
     2     6                           2
    / \   / \                           \
   1  3  5   7                            3 ...

height 3                     height 7
search visits <= 3 nodes     search visits up to 7

1,000,000 nodes
  balanced    height ~20     operations ~20 steps
  degenerate  height 1,000,000  operations ~1,000,000 steps

Recap: four walks and one number

A short chapter summary, because the vocabulary is most of the difficulty.

Pre-order handles a node before its children - use it to copy or serialise, since the parent must exist before children attach to it. Post-order handles children first - use it to delete, or to compute anything that depends on subtree results like height or size. In-order sits between them, and on a search tree it emits values in sorted order.

Those three are all depth-first, and recursion gives them to you free because the call stack does the remembering. Level-order is breadth-first and needs a queue instead, which is chapter 7 arriving exactly where it was promised.

And the one number: height. Every cost in the next two lessons is O(height), so everything hinges on whether the tree stays balanced.