Tree Traversals

A traversal is a systematic way to visit every node in a tree exactly once. Because a tree branches, there is no single "next" node — you must decide, at each step, whether to go deep (follow a child all the way down) or go wide (finish the current level before descending).

That single decision splits traversals into two families: depth-first search (DFS), which plunges down one branch before backtracking, and breadth-first search (BFS), which sweeps level by level. DFS naturally uses a stack (or the call stack via recursion); BFS uses a queue.

The three DFS orders

DFS on a binary tree comes in three flavours, distinguished only by when you process the current node relative to its subtrees:

• Pre-order (node → left → right): process the node first. Great for copying a tree or serialising its structure top-down.
• In-order (left → node → right): process the node between its subtrees. On a binary search tree this yields the keys in sorted order.
• Post-order (left → right → node): process the node last. Ideal for deleting or freeing a tree, since you handle children before the parent.

function preorder(node, out = []) {
  if (!node) return out
  out.push(node.val)          // node
  preorder(node.left, out)    // left
  preorder(node.right, out)   // right
  return out
}

function inorder(node, out = []) {
  if (!node) return out
  inorder(node.left, out)     // left
  out.push(node.val)          // node
  inorder(node.right, out)    // right
  return out
}

function postorder(node, out = []) {
  if (!node) return out
  postorder(node.left, out)   // left
  postorder(node.right, out)  // right
  out.push(node.val)          // node
  return out
}

Doing DFS without recursion

Recursion is really just an implicit stack. When the tree is deep enough to risk a stack-overflow (or in languages without tail calls), swap in an explicit stack. Pre-order is the cleanest to convert: push right before left so left is popped first.

function preorderIterative(root) {
  if (!root) return []
  const out = [], stack = [root]
  while (stack.length) {
    const node = stack.pop()
    out.push(node.val)
    // push right first so left is processed next
    if (node.right) stack.push(node.right)
    if (node.left) stack.push(node.left)
  }
  return out
}

Level-order (BFS)

To visit nodes level by level, use a queue: dequeue a node, process it, then enqueue its children. Tracking the queue length at the start of each round lets you group nodes by level — the standard trick for "return values level by level" problems.

function levelOrder(root) {
  if (!root) return []
  const out = [], queue = [root]
  while (queue.length) {
    const level = []
    for (let n = queue.length; n > 0; n--) {
      const node = queue.shift()
      level.push(node.val)
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
    out.push(level)
  }
  return out
}