Loading video…
hashing and treessolid

Binary Trees and the Four Traversals

Every data structure in this course so far has been a line. The array is a line of slots. The string is a line of bytes. The linked list is a line of nodes. The stack and the queue are lines with bouncer policies about which end you may touch. Even the hash table, the most sophisticated thing we've built, is an array wearing a key-to-index converter: a line with a clever doorman.

A line is one shape, and it's the wrong shape twice over.

First, your data is frequently not a line. Open your browser's dev tools on any page: the HTML document is elements containing elements containing elements, a hierarchy. Your filesystem is directories containing directories. A JSON payload is values nested inside values. An org chart, a comment thread, the syntax of the code you write: lesson 9 already named this shape (nesting) and showed that the code for it recurses. This lesson is about the structure for it.

Second, performance. Lesson 12 ended with a want list: keep every key sorted, answer range queries and smallest-key, and still run in logarithmic time. Lesson 1 told you where log n comes from, the only place it ever comes from: each step halves what's left. Binary search (lesson 8) could halve because it could jump to the middle of a sorted array. To halve inside a linked structure, every node needs a branch point: a place where one comparison can send you one way or the other. A line has no left or right. A tree is what you get when you give every node both.

This lesson builds the branching structure and learns the four ways to walk it. The rule that makes it searchable is deliberately missing until next lesson; you'll feel the gap, and that's the point.

The shape

Here is the tree this whole lesson walks. Six nodes, deliberately not in any sorted arrangement:

        4
      /   \
     9     2
    / \     \
   7   1     8

The vocabulary, demonstrated on it rather than defined in the abstract:

  • 4 is the root: the one node nothing points to, the entry point, the analog of a linked list's head. Computer science trees grow downward; nobody apologizes for this anymore.
  • 9 and 2 are the children of 4, and 4 is their parent. Every node except the root has exactly one parent. That single-parent rule is what makes this a tree rather than a general graph: no two branches ever merge back together, no cycles, every node reachable by exactly one path from the root. (Graphs, where those rules relax, are lesson 17.)
  • 7, 1, and 8 are leaves: nodes with no children. The bottom edge of the structure.
  • Take 9 together with its children 7 and 1, and you're holding a complete, self-sufficient tree in its own right: a subtree. Every node is the root of its own subtree. This innocuous observation is about to become the engine of the entire lesson.
  • The height of a tree is the longest root-to-leaf path, counted in edges: here, 2 (from 4 down to 7, or 1, or 8). The depth of a node is its distance from the root: node 1 sits at depth 2.

Binary means every node has at most two children, distinguished as left and right. Real-world trees are rarely binary (a directory holds any number of entries, a DOM node any number of children), but binary is the teaching case: two children is the smallest number that branches, everything here generalizes to n children mechanically, and the structures built in the next two lessons are binary on purpose.

A structure that is its own definition

Lesson 9 made a promise: trees are the data structure that is nesting, and recursion would be the native language there. Time to cash it, and the cashing happens in the definition itself. A binary tree is either:

  • empty, or
  • a node holding a value, a left subtree, and a right subtree.

Read that again. The definition refers to itself, twice. Every structure before this one was defined by arrangement (slots in a row, nodes in a chain); this is the first one defined the way recursive functions are written, with a base case (empty) and a self-reference (the two subtrees). Recursion stops being a technique you apply to a problem and becomes the literal shape of the data.

In memory, the node is nothing new. Lesson 5's linked list node was a value plus one next pointer. A binary tree node is a value plus two:

node:
    value
    left    # pointer to a node, or null
    right   # pointer to a node, or null

A linked list node with two nexts. That's the whole structural inventory. Null plays the role of the empty tree, exactly as it played end-of-chain in lesson 5.

The payoff of a recursive definition is that algorithms fall out of it almost passively. What's the height of a tree? An empty tree has height -1 (a convention chosen so that a single lonely node gets height 0; some books count nodes instead of edges, pick one and stay consistent). A non-empty tree is one edge taller than its taller subtree:

function height(t):
    if t is empty: return -1                       # base case
    return 1 + max(height(t.left), height(t.right)) # the leap, twice

Run it against lesson 9's two rules. Base case: the empty tree, handled first. Progress: both recursive calls descend into strictly smaller subtrees, and the tree has a bottom. So take the leap of faith: trust that height(t.left) and height(t.right) return the right answers, and the combining step is one line of arithmetic. On the six-node tree: the subtree under 9 has height 1, the subtree under 2 has height 1, so the whole thing is 1 + max(1, 1) = 2. Correct, and we never traced a frame.

Counting nodes is the same skeleton with different arithmetic:

function count(t):
    if t is empty: return 0
    return 1 + count(t.left) + count(t.right)

Handle empty. Trust the two smaller answers. Combine. Nearly every tree algorithm you will ever write is that three-line skeleton wearing different combine logic, and that's not a coincidence, it's the definition echoing back.

Four ways to walk one tree

Now the marquee. A traversal visits every node exactly once, the tree equivalent of looping over an array, and every traversal below is O(n): n visits, no way around it. But here's what's new. A line has one sensible visiting order: front to back. A tree, at every single node, has three pieces of business: the node itself, the left subtree, the right subtree. The subtrees stay in left-then-right order by convention, so the only question is when you handle the node: before both subtrees, between them, or after both. Three answers, three depth-first traversals. Then there's a fourth order that refuses the question entirely.

Same six-node tree for all four. Watch the sequences differ.

Pre-order: node, left, right

function preorder(t):
    if t is empty: return
    visit(t.value)        # node first
    preorder(t.left)
    preorder(t.right)

On our tree: visit 4, then the whole left subtree (9, then 7, then 1), then the whole right subtree (2, then 8). Sequence: 4 9 7 1 2 8.

Pre-order means parents before children: top-down. That's the order for any job where a child needs its parent to exist first. Copying or serializing a tree is pre-order, because you must create a node before you can attach children to it; write a pre-order sequence to disk (with markers for the empty spots) and the original tree can be rebuilt from it unambiguously. The tree command's output, that indented directory listing, is a pre-order walk: each directory printed before its contents.

In-order: left, node, right

function inorder(t):
    if t is empty: return
    inorder(t.left)
    visit(t.value)        # node in the middle
    inorder(t.right)

Drain the entire left subtree, then the node, then the right subtree. On our tree: 7, then 9, then 1 (that finishes 4's left subtree), then 4, then 2's side: 2 has no left child, so 2, then 8. Sequence: 7 9 1 4 2 8.

Look at that output. It's nothing. No story, no pattern, an arbitrary shuffle, and that's honest: on a tree with no rule about where values live, in-order has nothing to say. Remember this one anyway. Next lesson it does something almost magical.

Post-order: left, right, node

function postorder(t):
    if t is empty: return
    postorder(t.left)
    postorder(t.right)
    visit(t.value)        # node last

Both subtrees fully handled before the node itself. Sequence: 7 1 9 8 2 4. The root goes last.

Post-order means children before parents: bottom-up, the order for any job where the parent's answer is built from the children's answers. And you have already run one. Lesson 9's directory-size function, the du walk: the size of a directory is the sizes of its children, computed first, then summed at the parent. That filesystem walk was a post-order traversal; now it has its name. Same logic for freeing a tree in a manual-memory language: free the children before the parent, because the parent holds the only pointers to them, and freeing it first orphans everything below.

The showpiece example is the expression tree. The expression (3 + 4) * 2 is a tree, and the parentheses you write are just instructions for building it:

        *
      /   \
     +     2
    / \
   3   4

Operators are internal nodes; numbers are leaves. To evaluate it, you cannot apply * until both of its operands are known, and the left operand is itself an expression. So: evaluate the left subtree (3, then 4, then apply +, giving 7), evaluate the right subtree (2), then apply *: 14. Values become available in exactly post-order. This is not a toy. Your compiler parses source code into an abstract syntax tree (an AST: expressions containing expressions, lesson 9's nesting), and evaluating, type-checking, and constant-folding that tree are post-order walks, because an expression's type and value depend on its children's.

Level-order: floor by floor

The fourth traversal refuses to pick a branch and follow it down. It visits by depth: the root, then everything at depth 1, then everything at depth 2. On our tree: 4, then 9 2, then 7 1 8.

No recursion this time, and no stack. Level-order runs on lesson 6's queue:

function level_order(root):
    queue = new queue
    enqueue(root)
    while queue is not empty:
        node = dequeue()
        visit(node.value)
        if node.left is not empty:  enqueue(node.left)
        if node.right is not empty: enqueue(node.right)

Trace it. Queue starts as [4]. Dequeue 4, visit it, enqueue its children: [9, 2]. Dequeue 9, visit, enqueue 7 and 1: [2, 7, 1]. Dequeue 2, visit, enqueue 8: [7, 1, 8]. Then 7, 1, 8 come off in order, childless, adding nothing. The FIFO discipline is the level ordering: children join the back of the line, so everything at the current depth gets served before anything deeper. Lesson 6 promised the queue would run a search that explores level by level; this is the first payment on that promise. The full version, breadth-first search over graphs, is lesson 17.

So the family splits cleanly. Three traversals are depth-first: they commit to a branch and follow it to the bottom, and they run on a stack (the call stack, or an explicit one). One is breadth-first: it sweeps wide, and it runs on a queue. Hold that split; the next section makes it sharper than it looks.

The stack you can see

Lesson 9 established the correspondence: any recursion can become a loop plus an explicit stack, because the call stack was just a stack all along. Apply it to pre-order:

function preorder_iterative(root):
    stack = new stack
    push(root)
    while stack is not empty:
        node = pop()
        visit(node.value)
        if node.right is not empty: push(node.right)
        if node.left is not empty:  push(node.left)

Push right before left, so left pops first and the left subtree is fully handled before the right, matching the recursive order. Now put this function next to level_order above. Same skeleton, line for line: seed the container with the root, loop until empty, take one out, visit it, put its children in. The only difference is the container. Swap the queue for a stack and breadth-first becomes depth-first. The stack hoards the newest thing and digs; the queue serves the oldest thing and sweeps. The data structure choice is not an implementation detail of the traversal. It is the traversal. Lesson 17 will make this exact statement about searching graphs, and you'll have seen it here first.

The recursion has a space bill, and lesson 9 taught you how to read it: depth of recursion equals frames on the stack equals memory. For a traversal, the maximum depth is the height of the tree. A reasonably bushy tree with a million nodes is about 20 levels deep (lesson 1's halving arithmetic, run in reverse: each level roughly doubles the node count). Twenty frames is nothing. But nothing in this lesson's definition forces a tree to be bushy. A tree where every node has only a right child is, by the definition, a perfectly legal binary tree, and it's a linked list in a costume: height n, recursion depth n, and every per-height promise in sight quietly becomes O(n). Hold that thought. It is next lesson's whole subject.

One representation note before the code. Everything here is nodes and pointers, which means traversals pay lesson 2's toll: each child link is a pointer chase, and nodes scattered across the heap commute rather than stream. There is one famous family of trees that escapes: a complete tree (every level full, last level packed to the left) can be stored in a plain array with index arithmetic standing in for the pointers, no nodes at all. That trick gets its own lesson: it's how lesson 15 builds the heap.

The real code

The videos stay in pseudocode; here are the node and all four traversals in the three languages this course carries. The TypeScript includes the explicit-stack pre-order.

interface TreeNode {
  value: number
  left: TreeNode | null
  right: TreeNode | null
}
 
function preorder(t: TreeNode | null, out: number[] = []): number[] {
  if (t === null) return out // empty tree: nothing to do
  out.push(t.value) // node
  preorder(t.left, out) // left
  preorder(t.right, out) // right
  return out
}
 
function inorder(t: TreeNode | null, out: number[] = []): number[] {
  if (t === null) return out
  inorder(t.left, out)
  out.push(t.value) // node in the middle
  inorder(t.right, out)
  return out
}
 
function postorder(t: TreeNode | null, out: number[] = []): number[] {
  if (t === null) return out
  postorder(t.left, out)
  postorder(t.right, out)
  out.push(t.value) // node last
  return out
}
 
function levelOrder(root: TreeNode | null): number[] {
  const out: number[] = []
  if (root === null) return out
  const queue: TreeNode[] = [root]
  let head = 0 // moving head index: lesson 6's fix, shift() is O(n)
  while (head < queue.length) {
    const node = queue[head++] // dequeue
    out.push(node.value)
    if (node.left) queue.push(node.left)
    if (node.right) queue.push(node.right)
  }
  return out
}
 
function preorderIterative(root: TreeNode | null): number[] {
  const out: number[] = []
  if (root === null) return out
  const stack: TreeNode[] = [root]
  while (stack.length > 0) {
    const node = stack.pop()! // newest in, first out: dig deep
    out.push(node.value)
    if (node.right) stack.push(node.right) // right first...
    if (node.left) stack.push(node.left) // ...so left pops first
  }
  return out
}

The three recursive walks are the same six lines with out.push moved: that single line's position is the entire difference between pre, in, and post. levelOrder dequeues with a moving head index instead of Array.prototype.shift(), because lesson 6 already convicted shift of being O(n) per call. And preorderIterative against levelOrder is the family split made visible: identical loop, pop from the back versus read from the front, depth versus breadth.

The Go version's nil check leads every function: Go's zero-value pointer plays the empty tree exactly as the definition demands. The queue is the slice idiom from lesson 6 (queue[1:] advances the head without copying the elements; the backing array is shared).

C++ gets one extra function the garbage-collected languages don't need: free_tree, and it is forced to be post-order. Delete the parent first and the only pointers to its children are gone; the memory leaks. The traversal orders aren't academic taxonomy; sometimes the problem leaves you exactly one of them.

Where this shows up in production

  • The DOM, constantly. Every document.querySelector call is a depth-first walk of the element tree; "document order", the order CSS and selectors are defined against, is pre-order. React's reconciliation is one more line here: a re-render walks the component tree comparing the new tree against the old one.
  • Every tool that touches your code. Prettier parses your file into an AST, walks the tree, and prints it back. ESLint exposes the walk directly: a lint rule registers visitors that fire on entering a node (the pre-order moment) and exiting it (the post-order moment), which is also the honest generalization of this lesson: a real depth-first walk passes each node twice, and "pre" versus "post" is just which visit you do your work in. Type checkers work bottom-up, post-order, because the type of a + b needs the types of a and b first.
  • Serialization. JSON.stringify walks a value tree; emitting { on the way in and } on the way out is pre- and post-order work on the same walk.
  • The filesystem tools. tree and recursive listings print pre-order; du sums post-order; and find has a -depth flag whose entire job is switching the walk from pre-order to post-order, because deleting (rm -r, which needs children gone before the directory) can't run in any other order.

Six nodes, no shortcuts

Take stock of what the tree did and didn't buy. The structure branches, the definition recurses, and one six-node tree yielded four distinct visiting orders, each the right answer to a different job: top-down for copying and listing, bottom-up for sizing and freeing and evaluating, level-by-level for nearest-first. But notice what never happened in this entire lesson: we never found anything fast. Ask whether 8 is somewhere in the tree and nothing here beats visiting nodes until you bump into it, O(n), exactly what the line cost. The branch points are there, a left and a right at every node, a fork that could discard half the structure per comparison. They're just not wired to anything, because values are allowed to live anywhere. Next lesson adds the single rule that wires them up: an ordering invariant on where values may sit, which turns every node's comparison into binary search's halving step, makes the tree the sorted-and-still-logarithmic structure lesson 12 was asking for, and finally fires the gun in-order has been quietly holding. It also has a failure mode, and you've already met it: that chain-shaped tree of height n. Binary search trees, and the degenerate case, next.

Command Palette

Search for a command to run...