Binary Trees & Traversals

The 10-second versionCopy Anchor Link

A binary tree is what you get when a linked list is allowed to branch: each node holds a value plus up to two pointers, left and right. That one change turns a straight line into a hierarchy — the shape of file systems, arithmetic expressions, and decision diagrams. A flat array has one obvious way to walk it start to finish; a tree doesn't, so "visit every node" splits into four natural orders. Two of them (depth-first) differ only in when you touch a node relative to its children, a third goes floor by floor, and each one answers a different question. Get those four orders into your bones and every later tree page becomes "which order do I need?"

Why this existedCopy Anchor Link

For the first couple of decades of computing, data lived in flat rows — an array of numbers, a punched card deck, a reel of tape. But the world is stuffed with hierarchies: an org chart, a family tree, the grammar of a sentence, and the precedence in 2 + 3 × 4 (which is not the same as (2 + 3) × 4). You cannot flatten those into a line without destroying the "contains" relationships that gave them meaning.

Mathematicians arrived first. In 1847 Gustav Kirchhoff, analyzing electrical networks, wrote down structures we would now call trees, and the idea stuck; Arthur Cayley counted rooted trees in 1857, turning them into a proper object of study. But it was compilers, in the late 1950s, that made trees unavoidable in software: the only sane way to represent (a + b) × c is a tree where multiplication sits above addition, because the addition must happen first.

That raised the quietly deep question: once you have a tree, how do you visit it? The vocabulary we still use — preorder, inorder, postorder for the depth-first walks, and level-order for the wide one — was settled in the late 1960s, most influentially in Donald Knuth's The Art of Computer Programming (Volume 1, 1968). It mattered then for a very practical reason: a compiler must emit instructions, evaluate expressions, and free memory, and each of those is a different traversal order over the very same tree.

Why it mattered: the order is not cosmetic. Two traversals of an identical tree can drive a calculator or corrupt your data. Choosing the order is the algorithm.

Inside the inventor's headCopy Anchor Link

Start from the dumbest possible goal — "touch every node exactly once." On a linked list that's a while loop. On a tree, where do you even begin? You begin at the root, then there are two children, then each of those has two... The branching is the whole problem.

The first real insight is that a tree is recursive, so the walk should be recursive too. A tree is either empty, or a node whose left and right pieces are themselves trees. So "traverse a tree" is literally: traverse the left subtree, do something with this node, traverse the right subtree. The recursion writes itself.

The second insight — the one that makes people go "ohhh" — is that the position of the work is the only thing that changes. Do your work before recursing into the children and you get preorder. Sit it between the two recursions and you get inorder. Put it after both and you get postorder. One skeleton, three algorithms.

Then watch what happens the first time you point that elegant recursion at a million-node tree. It dies — the call stack, which had been holding your path for free, overflows. That's the moment you learn to trade the language's stack for one you manage yourself:

// Naive: the obvious version — the call stack carries the path.function inorder(n, out = []) {  if (!n) return out;  inorder(n.left, out);  out.push(n.value);         // visit between the two subtrees  inorder(n.right, out);  return out;}

// Improved: an explicit array is our stack — no recursion depth limit.function inorderIter(root) {  const out = [], stack = [];  let cur = root;  while (cur || stack.length) {    while (cur) { stack.push(cur); cur = cur.left; } // go as far left as possible    cur = stack.pop();    out.push(cur.value);                             // visit    cur = cur.right;                                 // then head right  }  return out;}

The final approachCopy Anchor Link

The tree we'll useCopy Anchor Link

Four traversals, one tree. Everything below runs against these seven nodes:

The four depth-first orders are the same skeleton with the visit moved around. Level-order abandons depth entirely and reads the tree row by row:

The algorithm, as a flowCopy Anchor Link

Depth-first traversal is nothing more than "recurse left, visit, recurse right" — here drawn for inorder, the version you'll meet most:

The invariants that make it correctCopy Anchor Link

1. Each node is visited exactly once. The recursion never visits a subtree twice, because each left and right pointer is followed a single time.
2. Depth-first stays inside a subtree until it's finished. When inorder(node.left) returns, every node in the left subtree has already been visited — that's why the "visit between the two recursions" produces the order it does.
3. A traversal does exactly n visits for n nodes — no more, no less — so every one of these is Θ(n) in time.
4. Recursion depth equals the height h. That's O(log n) for a balanced tree and O(n) for a degenerate one — a distinction that gets its own pages shortly.

A worked traceCopy Anchor Link

Walk inorder on the tree above, reading left to right:

• Enter 50, go left into 30, go left into 20. 20 has no children, so visit 20.
• Back up to 30: its left is done, so visit 30, then go right into 40. 40 has no children, so visit 40. The whole 30 subtree is finished.
• Back up to 50: its left is done, so visit 50, then go right into 70.
• Mirror it: 70's left (60) → visit 60 → 70 → 70's right (80) → visit 80.

You read out 20, 30, 40, 50, 60, 70, 80 — perfectly sorted, because this tree happens to be ordered. That "inorder gives sorted output" fact is the entire reason the next page exists.

It in codeCopy Anchor Link

All four traversals, once, in each dialect. The only difference between the first three functions is where the visit line sits.

class Node {  constructor(value) { this.value = value; this.left = null; this.right = null; }}function preorder(n, out = [])  { if (!n) return out; out.push(n.value); preorder(n.left, out);  preorder(n.right, out); return out; }function inorder(n, out = [])   { if (!n) return out; inorder(n.left, out);   out.push(n.value); inorder(n.right, out); return out; }function postorder(n, out = []) { if (!n) return out; postorder(n.left, out);  postorder(n.right, out); out.push(n.value); return out; }function levelorder(root) {  const out = [];  const q = root ? [root] : [];  for (let i = 0; i < q.length; i++) {   // an index pointer over an array == a queue    const n = q[i];    out.push(n.value);    if (n.left)  q.push(n.left);    if (n.right) q.push(n.right);  }  return out;}const root = new Node(50);root.left = new Node(30); root.right = new Node(70);root.left.left = new Node(20); root.left.right = new Node(40);root.right.left = new Node(60); root.right.right = new Node(80);console.log(preorder(root));   // [50, 30, 20, 40, 70, 60, 80]console.log(inorder(root));    // [20, 30, 40, 50, 60, 70, 80]console.log(postorder(root));  // [20, 40, 30, 60, 80, 70, 50]console.log(levelorder(root)); // [50, 30, 70, 20, 40, 60, 80]

Cost tableCopy Anchor Link

The time never changes: you must look at every node once. The space is where the orders differ, and where a bad tree shape quietly turns O(log n) into O(n).

Where you meet it todayCopy Anchor Link

• Compilers and calculators. An expression is a tree; evaluating it is a postorder walk (the operator fires after its operands are ready). Emitting RPN is just "print in postorder."
• Serialization. Saving a tree to bytes and rebuilding it is a preorder walk with markers for absent children — the classic way to flatten a hierarchy to a file.
• File systems and the DOM. Listing a directory tree, or React diffing a component tree, is a depth-first walk you trigger every day without naming it.
• Heap layout. A binary heap (last page's heaps) stores its level-order traversal directly in a flat array, so parent(i) is just i / 2.

// Expression tree; postorder evaluation is exactly how a stack machine works.const evalExpr = (e) => {  if (!e.op) return e.value;                // a leaf → its number  const l = evalExpr(e.left), r = evalExpr(e.right);  return { "+": l + r, "-": l - r, "*": l * r }[e.op];};

RecapCopy Anchor Link

• A binary tree branches: each node carries a value and up to two child pointers, and it is recursive by nature — every subtree is a tree.
• Depth-first traversal is one skeleton with the visit moved: before the children (preorder), between them (inorder), after them (postorder).
• Level-order trades depth for breadth and uses a queue; depth-first uses recursion or an explicit stack.
• All traversals are Θ(n) in time; the real difference is extra space, which is O(log n) only when the tree is balanced.
• Inorder on an ordered tree reads out sorted — remember that, it's the next page.

Next up: Binary Search Trees — where the order between parents and children becomes a rule you can search with.