Tree Traversals

How it works, step by step

1. 1

   All three traversals share one recursive skeleton: at a node, handle the left subtree, handle the right subtree, and at some moment visit the node itself (print it, process it).

2. 2

   Pre-order visits first, then goes left, then right. The root comes out first, then each subtree's root before its contents - top-down.

3. 3

   In-order goes left, visits, then goes right. On a binary search tree every smaller value is out before the node, every bigger one after - so the output is sorted.

4. 4

   Post-order goes left, goes right, and visits last. A node only comes out after everything below it - children always before parents.

5. 5

   The recursion stack remembers the way back: a node waits on it while its left side finishes. The stack never grows deeper than the tree's height, so extra space is O(h).

6. 6

   Every node is visited exactly once and every edge is walked twice (down and back up), so all three orders take O(n) time.

The code, in JavaScript

const node = (value, left = null, right = null) => ({ value, left, right });

// The BST from the animation: insert 8, 3, 10, 1, 6, 14, 4.
const tree = node(8,
  node(3, node(1), node(6, node(4))),
  node(10, null, node(14))
);

// Pre-order: visit BEFORE the children. Root first, top-down.
// The order for COPYING or serializing a tree.
function preOrder(n, out = []) {
  if (!n) return out;
  out.push(n.value);        // visit
  preOrder(n.left, out);
  preOrder(n.right, out);
  return out;
}

// In-order: visit BETWEEN the children.
// On a BST, this is SORTED output.
function inOrder(n, out = []) {
  if (!n) return out;
  inOrder(n.left, out);
  out.push(n.value);        // visit
  inOrder(n.right, out);
  return out;
}

// Post-order: visit AFTER the children. Parents last.
// The order for DELETING a tree safely: children go first.
function postOrder(n, out = []) {
  if (!n) return out;
  postOrder(n.left, out);
  postOrder(n.right, out);
  out.push(n.value);        // visit
  return out;
}

preOrder(tree);   // → [8, 3, 1, 6, 4, 10, 14]  (root first)
inOrder(tree);    // → [1, 3, 4, 6, 8, 10, 14]  (sorted!)
postOrder(tree);  // → [1, 4, 6, 3, 14, 10, 8]  (root last)

Dry run: in-order on the 7-node BST

The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.

• In-order output is sorted only on a binary search tree. On a random binary tree the in-order sequence means nothing. Interviewers love handing you a plain tree and waiting for you to claim it is sorted.
• Recursion depth is the tree's height, not log n. A degenerate tree - every node with a single child, a linked list in disguise - makes it O(n) deep, and at some ten thousand nodes JavaScript throws 'Maximum call stack size exceeded'.
• Pre-order is the only order that can rebuild the tree from one flat list - and even then only with null markers (or value bounds, on a BST). An in-order list alone can never rebuild it: many different trees share the same in-order sequence.
• 'Visit' means *process*, not *pass through*. The walk passes each node up to three times; pre, in and post only name which pass does the work. Mix those two ideas up and all three orders look like the same algorithm.

Tree Traversals vs. its closest relatives