Traversals: why in-order comes out sorted

A BST can be walked in the same four orders as any binary tree — but in a BST each order means something. The most important: an in-order walk (left subtree, node, right subtree) visits the values in sorted order, because everything on the left is smaller and everything on the right is bigger. Half of all BST interview questions are this one fact in disguise.

What each order is for in a BST

1. In-order with recursion

1function inorder(root) {2  const out = [];3  const walk = (node) => {4    if (node === null) return;5    walk(node.left);              // everything smaller first6    out.push(node.val);           // then the node7    walk(node.right);             // then everything bigger8  };9  walk(root);10  return out;11}

Time O(n), space O(h) for the call stack.

2. In-order with an explicit stack

The recursion's call stack can be made explicit: go left as far as possible, pushing every node on the way; pop one, visit it, then do the same from its right child. The stack always holds the nodes still waiting for their turn — at most one per level. This version can also be paused after any value, which is exactly what the BST Iterator problem needs.

1function inorder(root) {2  const out = [];3  const stack = [];4  let node = root;5  while (node !== null || stack.length > 0) {6    while (node !== null) {       // go left as far as possible,7      stack.push(node);           // remembering each node on the way8      node = node.left;9    }10    node = stack.pop();           // the smallest value not visited yet11    out.push(node.val);12    node = node.right;            // then everything just bigger than it13  }14  return out;15}

Time O(n), space O(h). Every node is pushed once and popped once.

3. Morris traversal: no stack at all

Morris traversal visits in-order with O(1) extra memory by borrowing the tree's own empty pointers. Before going left from a node, find its predecessor (the rightmost node of its left subtree) and point that node's empty right at the current node — a temporary thread back up. When the walk later reaches the thread, it knows the left side is done: it removes the thread, visits the node and goes right. The tree ends up exactly as it started.

1function inorder(root) {2  const out = [];3  let node = root;4  while (node !== null) {5    if (node.left === null) {6      out.push(node.val);                 // nothing smaller left: visit, go right7      node = node.right;8      continue;9    }10    let pred = node.left;                 // the rightmost node of the left subtree11    while (pred.right !== null && pred.right !== node) pred = pred.right;12    if (pred.right === null) {13      pred.right = node;                  // thread back to here, then do the left side14      node = node.left;15    } else {16      pred.right = null;                  // the left side is done: remove the thread,17      out.push(node.val);                 // visit this node, go right18      node = node.right;19    }20  }21  return out;22}

Time O(n), space O(1). Each edge is walked at most a few times while finding predecessors, so it's still linear. It temporarily changes the tree, so it isn't safe while another thread reads it.

Pre-order, post-order and level order

These are written exactly as for any binary tree — the Binary Tree course walks through each with a simulator. In short:

pre-order:   visit(node); walk(node.left); walk(node.right)
post-order:  walk(node.left); walk(node.right); visit(node)
level order: a queue: pop a node, visit it, push its children

Comparing the in-order approaches