DSAMonth 1 · Week 4

Day 19: Trees: DFS (Depth-First Search) Traversal

Master the three DFS orderings (pre/in/post) both recursively and iteratively, and know which one each problem type needs.

Mark this day complete

Study

Concepts

Three orderings of the same traversal

DFS goes as deep as possible before backtracking. The three standard orderings differ only in WHEN you process (visit) the current node relative to recursing into children: Preorder = process node, then left, then right (good for copying/serializing a tree top-down). Inorder = left, process node, right (on a Binary SEARCH Tree, this visits nodes in sorted order — a hugely useful fact). Postorder = left, right, then process node (good for anything that needs children fully resolved first, like computing subtree sizes/heights or safely deleting a tree).

Every recursive DFS traversal implicitly uses the Call Stack as its stack (Day 1). An iterative version makes that stack explicit with your own array, which is required when recursion depth could exceed the engine's call stack limit on very deep/unbalanced trees.

See It

Visualizations

Visualization

Inorder DFS on a Binary Search Tree yields sorted output

Visit order: left subtree → node → right subtree → 2, 5, 7, 10, 15, 20 (sorted!).

Build It

Code Examples

All three orderings, recursive

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

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

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

Iterative preorder — explicit stack instead of recursion

function preorderIterative(root) {
  if (!root) return [];
  const result = [];
  const stack = [root];

  while (stack.length) {
    const node = stack.pop();
    result.push(node.val);
    // Push right FIRST so left is processed first (stack is LIFO)
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  return result;
}

Postorder use case: compute height of every subtree

function annotateHeights(node) {
  if (!node) return -1; // empty subtree has height -1 by convention

  const leftHeight = annotateHeights(node.left);   // needs children resolved first
  const rightHeight = annotateHeights(node.right);  // — this IS postorder
  node.height = 1 + Math.max(leftHeight, rightHeight);
  return node.height;
}

Remember

Key Takeaways

Preorder: process-left-right — great for serialization/cloning. Inorder: left-process-right — sorted order on a BST. Postorder: left-right-process — needed when a node depends on its children's results.
Recursive DFS uses the real Call Stack implicitly; iterative DFS uses your own array as an explicit stack.
For iterative preorder, push right before left so the stack pops left first.
Postorder is the pattern for "compute X for a node using X of its children" (height, size, sum, diameter).
Pick the ordering by asking "do I need to know about my children before or after I process myself?"

Do It

Practice

1Implement inorder and postorder traversal iteratively (harder than preorder — needs a "last visited" tracking trick).
2Solve "Validate Binary Search Tree" using inorder traversal and checking strictly increasing order.
3Solve "Diameter of Binary Tree" using the postorder height-computation pattern, tracking a running max diameter as a side effect.