Tree traversals

Four ways to visit every node: preorder, inorder, postorder (all depth-first), and level order (breadth-first).

How it works

Preorder: node, then left, then right. Good for copying or serializing a tree. Inorder: left, node, right. On a BST this gives sorted order. Postorder: left, right, node. Good when children must be handled first (deleting, computing sizes). Level order uses a queue and is covered in the problems book. Any recursive traversal can be written with an explicit stack to avoid stack overflow on deep trees.

Reach for it when

• Need sorted order from a BST: inorder
• Serialize or clone: preorder
• Combine answers from children (height, sums): postorder
• Shortest path or levels: BFS

Copyconst node = (val, left = null, right = null) => ({ val, left, right });
function preorder(n, out = []) {
  if (n) {
    out.push(n.val);
    preorder(n.left, out);
    preorder(n.right, out);
  }
  return out;
}
function inorder(n, out = []) {
  if (n) {
    inorder(n.left, out);
    out.push(n.val);
    inorder(n.right, out);
  }
  return out;
}
function postorder(n, out = []) {
  if (n) {
    postorder(n.left, out);
    postorder(n.right, out);
    out.push(n.val);
  }
  return out;
}
function inorderIterative(root) {
  const out = [],
    stack = [];
  let cur = root;
  while (cur || stack.length) {
    while (cur) {
      stack.push(cur);
      cur = cur.left;
    } // go all the way left
    cur = stack.pop();
    out.push(cur.val);
    cur = cur.right;
  }
  return out;
}

Traps

• A skewed tree has h = n, so recursion depth can be n.
• Mixing up the orders: say the rule out loud before coding.