Trees and Traversals

Visiting every node of a binary tree has exactly one interesting decision:

When do you deal with the node itself — before its children, between them, or after both?

Everything else is the same three lines of recursion.

function walk(node: Node | null, out: number[]) {
  if (node === null) return;          // base case: nothing to do
  walk(node.left, out);
  out.push(node.value);               // <- move this line to change the order
  walk(node.right, out);
}

Move that one push above both recursive calls and you have pre-order; below both, post-order; where it is, in-order.

See the difference

The tree below is a binary search tree — everything left of a node is smaller, everything right is larger. Switch the visit position:

Which order, and why

In-order — sorted output from a search tree. It is the reason the binary search tree has the shape it does.

Pre-order — the root comes out first, so it serialises a tree in a form you can rebuild from. Copying a tree is pre-order.

Post-order — children first, so a node sees results from below. Anything of the form “compute something about my subtree” is post-order: height, total, deleting a tree, evaluating an expression.

Level-order — not a recursion at all. It needs a queue and answers questions about depth: shortest path in an unweighted tree, or printing row by row.

Recursion is a stack you did not have to write

The recursive version uses the call stack. The iterative version uses one you build yourself. They are the same algorithm:

function inorderIterative(root: Node | null): number[] {
  const out: number[] = [];
  const stack: Node[] = [];
  let node = root;

  while (node !== null || stack.length > 0) {
    while (node !== null) {        // go as far left as possible
      stack.push(node);
      node = node.left;
    }
    node = stack.pop()!;           // deepest unvisited left node
    out.push(node.value);
    node = node.right;             // then head right and repeat
  }

  return out;
}

Worth writing once, because it makes the memory cost visible. The stack holds up to one node per level, so both versions use $O(h)$ space where $h$ is the height.

Balance is the whole game

Notice that every cost above is stated in the height, not the number of nodes. Those only coincide when the tree is balanced.

Closing that gap is exactly what AVL trees, red-black trees and B-trees exist for — they rebalance as they go, so height stays $O(\log n)$ whatever order the data arrives in. It is why production code almost never uses a plain unbalanced search tree.