Tree Traversals (DFS/BFS) — The Complete Guide

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(
    val: number = 0,
    left: TreeNode | null = null,
    right: TreeNode | null = null
  ) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// Example tree:
//       1
//      / \
//     2   3
//    / \
//   4   5
// Preorder:  [1, 2, 4, 5, 3]  — root first
// Inorder:   [4, 2, 5, 1, 3]  — left, root, right
// Postorder: [4, 5, 2, 3, 1]  — children first, root last
// Level order: [1, 2, 3, 4, 5] — top to bottom, left to right

function solve(root: TreeNode | null): ResultType {
  // Base case: empty tree
  if (!root) return baseValue;

  // Recurse on children FIRST (postorder)
  const leftResult = solve(root.left);
  const rightResult = solve(root.right);

  // Compute current node's answer using children's results
  const currentResult = combine(leftResult, rightResult, root.val);

  // Optionally update a global answer (e.g., diameter)
  globalAnswer = Math.max(globalAnswer, someComputation);

  return currentResult;
}
// Examples:
// Height: return 1 + Math.max(left, right)
// Size:   return 1 + left + right
// Sum:    return root.val + left + right

function solve(node: TreeNode | null, parentInfo: InfoType): void {
  if (!node) return;

  // Process current node FIRST (preorder)
  // Use parentInfo to compute something for this node
  doSomething(node, parentInfo);

  // Pass updated info to children
  solve(node.left, updatedInfo);
  solve(node.right, updatedInfo);
}
// Examples:
// Path sum: pass remaining target down, check at leaf
// Depth:    pass current depth, increment for children
// Flatten:  process node, then recurse (careful with pointer rewiring)

function inorder(root: TreeNode | null): void {
  if (!root) return;

  inorder(root.left);       // visit left subtree

  // Process current node — this happens in SORTED ORDER for BST
  process(root.val);

  inorder(root.right);      // visit right subtree
}

// Iterative version (useful when you need to stop early):
function inorderIterative(root: TreeNode | null): number[] {
  const result: number[] = [];
  const stack: TreeNode[] = [];
  let curr = root;

  while (curr || stack.length) {
    // Go as far left as possible
    while (curr) {
      stack.push(curr);
      curr = curr.left;
    }
    // Process the node
    curr = stack.pop()!;
    result.push(curr.val);
    // Move to right subtree
    curr = curr.right;
  }

  return result;
}
// The iterative version is important for "kth smallest" where
// you want to stop after k nodes without visiting the entire tree.

function bfs(root: TreeNode | null): ResultType {
  if (!root) return baseValue;

  const queue: TreeNode[] = [root];
  const result: number[][] = [];

  while (queue.length) {
    const levelSize = queue.length;  // nodes at current level
    const currentLevel: number[] = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      currentLevel.push(node.val);

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(currentLevel);
  }

  return result;
}
// Key: capture queue.length BEFORE the inner loop.
// This tells you exactly how many nodes are at the current level.
// Variations:
// Right side view: take the LAST element of each level
// Zigzag: reverse every other level
// Min depth: return when you hit the first leaf

function diameterOfBinaryTree(root: TreeNode | null): number {
  let maxDiameter = 0;

  function height(node: TreeNode | null): number {
    if (!node) return 0;

    const left = height(node.left);
    const right = height(node.right);

    // Update global answer: diameter through this node
    maxDiameter = Math.max(maxDiameter, left + right);

    // Return height (what the parent needs)
    return 1 + Math.max(left, right);
  }

  height(root);
  return maxDiameter;
}
// The function RETURNS height (for parent's computation)
// but UPDATES diameter (the actual answer) as a side effect.
// This "return one thing, update another" pattern is very common:
// - Diameter: return height, update max path length
// - Max path sum: return max single-branch sum, update max any-path sum
// - Balanced tree: return height, update isBalanced flag

function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode
): TreeNode | null {
  // Base cases
  if (!root) return null;
  if (root === p || root === q) return root;

  // Postorder: search both subtrees
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  // If both subtrees found a target, current node is the LCA
  if (left && right) return root;

  // Otherwise, return whichever side found something
  return left ?? right;
}
// Why postorder? We need BOTH children's results before deciding.
// If left returns p and right returns q → root is LCA.
// If only one side returns non-null → LCA is deeper in that subtree.

function buildTree(
  preorder: number[],
  inorder: number[]
): TreeNode | null {
  // Map inorder values to indices for O(1) lookup
  const inMap = new Map<number, number>();
  inorder.forEach((val, i) => inMap.set(val, i));

  let preIdx = 0;

  function build(inLeft: number, inRight: number): TreeNode | null {
    if (inLeft > inRight) return null;

    const rootVal = preorder[preIdx++];
    const root = new TreeNode(rootVal);
    const inIdx = inMap.get(rootVal)!;

    root.left = build(inLeft, inIdx - 1);   // left subtree
    root.right = build(inIdx + 1, inRight);  // right subtree

    return root;
  }

  return build(0, inorder.length - 1);
}
// Key insight: preorder gives us roots in order (root, then left subtree
// roots, then right subtree roots). Inorder tells us the split point.
// The hash map makes root lookup O(1) instead of O(n).

Tree:
        1
       / \
      2   3
     / \   \
    4   5   6

═══════════════════════════════════════════════════
PREORDER (root → left → right) — "I go first"
═══════════════════════════════════════════════════
Visit 1 → go left
  Visit 2 → go left
    Visit 4 → no children, backtrack
  back to 2 → go right
    Visit 5 → no children, backtrack
  back to 2, backtrack
back to 1 → go right
  Visit 3 → go right
    Visit 6 → no children, backtrack
  back to 3, backtrack

Result: [1, 2, 4, 5, 3, 6]
Use: Serialization, copying tree structure

═══════════════════════════════════════════════════
INORDER (left → root → right) — "Left child goes first"
═══════════════════════════════════════════════════
Go left from 1 → go left from 2
  Visit 4 (no left child)
Visit 2
  Go right from 2 → Visit 5
Visit 1
  Go right from 1 → go left from 3 (no left)
  Visit 3
    Go right → Visit 6

Result: [4, 2, 5, 1, 3, 6]
Use: Sorted order in BST

═══════════════════════════════════════════════════
POSTORDER (left → right → root) — "Children go first"
═══════════════════════════════════════════════════
Go left from 1 → go left from 2
  Visit 4 (leaf)
  Go right from 2 → Visit 5 (leaf)
Visit 2 (both children done)
  Go right from 1 → go right from 3
    Visit 6 (leaf)
  Visit 3 (children done)
Visit 1 (both children done)

Result: [4, 5, 2, 6, 3, 1]
Use: Height, diameter, delete tree (children before parent)

═══════════════════════════════════════════════════
BFS / LEVEL ORDER — "Floor by floor"
═══════════════════════════════════════════════════
Queue: [1]
Level 0: process 1, enqueue 2, 3     → [1]
Queue: [2, 3]
Level 1: process 2, enqueue 4, 5
         process 3, enqueue 6        → [2, 3]
Queue: [4, 5, 6]
Level 2: process 4, 5, 6             → [4, 5, 6]

Result: [[1], [2, 3], [4, 5, 6]]
Use: Level-by-level processing, right side view, min depth

Tree:
        1
       / \
      2   3
     / \
    4   5

height(4) → left=0, right=0 → diameter through 4 = 0+0 = 0 → return 1
height(5) → left=0, right=0 → diameter through 5 = 0+0 = 0 → return 1
height(2) → left=1, right=1 → diameter through 2 = 1+1 = 2 → return 2
height(3) → left=0, right=0 → diameter through 3 = 0+0 = 0 → return 1
height(1) → left=2, right=1 → diameter through 1 = 2+1 = 3 ★ → return 3

maxDiameter = 3 (path: 4 → 2 → 1 → 3)

Key insight: The function RETURNS height (for the parent to use)
but UPDATES maxDiameter (the actual answer) at every node.
The diameter through any node = leftHeight + rightHeight.
The answer is the maximum diameter across ALL nodes.

Tree:
        5
       / \
      3   7
     / \   \
    1   4   9

validate(5, -∞, +∞) → 5 is in range ✓
  validate(3, -∞, 5) → 3 is in range ✓
    validate(1, -∞, 3) → 1 is in range ✓
      validate(null) → true (base case)
      validate(null) → true
    validate(4, 3, 5) → 4 is in range ✓
      validate(null) → true
      validate(null) → true
  validate(7, 5, +∞) → 7 is in range ✓
    validate(null) → true
    validate(9, 7, +∞) → 9 is in range ✓
      validate(null) → true
      validate(null) → true

All nodes valid → return true

This is PREORDER with bounds: parent passes [min, max] range
to children. Left child gets [min, parent.val]. Right child
gets [parent.val, max]. If any node is outside its range → false.

What does the problem ask?
├── Process nodes level by level?
│   → BFS (queue + level-size trick)
│   ├── Right/left side view → last/first node per level
│   ├── Zigzag → reverse every other level
│   └── Min depth → return at first leaf encountered
├── Need sorted order from BST?
│   → Inorder DFS (left → root → right)
│   ├── Kth smallest → stop after k nodes (iterative preferred)
│   └── Validate BST → check strictly increasing sequence
├── Need children's results to compute parent's answer?
│   → Postorder DFS (bottom-up)
│   ├── Height / depth → 1 + max(left, right)
│   ├── Diameter → return height, update global max(left + right)
│   ├── Balanced check → return -1 as sentinel for unbalanced
│   ├── LCA → if both sides non-null, current is LCA
│   └── Subtree sum → root.val + left + right
├── Need to pass info from parent to children?
│   → Preorder DFS (top-down)
│   ├── Path sum → pass remaining target, check at leaf
│   ├── BST validation → pass [min, max] bounds
│   ├── Serialize → write node value, recurse children
│   └── Flatten → process node, then recurse
└── Not sure?
    → Default to postorder DFS. Most tree problems are bottom-up.
      If that feels wrong, try preorder or BFS.