Tree & Graph Puzzles

Level order traversal (BFS) visits all nodes at depth d before any node at depth d+1, processing the tree left-to-right, layer by layer.

Use a queue. Start by enqueuing the root. For each level, determine the queue size, dequeue exactly that many nodes (the current level), and enqueue their children for the next level.

The snapshot of queue size at the start of each iteration isolates exactly one level of nodes.

Time complexity is O(n) since every node is enqueued and dequeued exactly once; space is O(w) where w is the maximum width.

function levelOrder(root) {
  if (!root) return [];
  let queue = [root], result = [];
  while (queue.length) {
    let level = [], size = queue.length;
    for (let i = 0; i < size; i++) {
      let node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

Size snapshot per level: Capturing queue.length before the inner loop ensures only nodes from the current level are processed, regardless of how many children are added.

Level order traversal is the foundation for many tree problems: zigzag traversal, finding level averages, right side view, and more.

A binary tree is symmetric (a mirror of itself) if the left subtree is a mirror reflection of the right subtree around the root.

Recursively compare corresponding node pairs: the root's left child with the root's right child, the left-left with right-right, and the left-right with right-left.

Two subtrees are mirrors if both are null (symmetric), one is null and the other is not (asymmetric), or their values differ (asymmetric).

Time complexity is O(n) and space is O(h) for the recursion stack.

function isSymmetric(root) {
  function mirror(a, b) {
    if (!a && !b) return true;
    if (!a || !b) return false;
    return a.val === b.val && mirror(a.left, b.right) && mirror(a.right, b.left);
  }
  return mirror(root, root);
}

Cross-comparison: Instead of comparing left with left and right with right, compare left with right subtrees at each level — this captures the mirror property.

An iterative BFS version uses a queue of pairs: each iteration dequeues two nodes and checks their values and enqueues their children in mirror order.

A root-to-leaf path sum is the sum of all node values along a path from the root down to a leaf (a node with no children).

Use DFS. At each node, subtract the node's value from the target sum. At a leaf node, check if the remaining sum is zero — if so, a matching path was found.

Null nodes return false immediately — if you reach null without finding a leaf match, that path did not work out.

The recursion depth is O(h) and time complexity is O(n) in the worst case (balanced tree visits all nodes).

function hasPathSum(root, sum) {
  if (!root) return false;
  if (!root.left && !root.right) return sum === root.val;
  return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}

Check at leaf, not just null: Test sum === root.val only when the node is a leaf — checking at null would count sums along internal paths that do not reach a leaf.

To collect all such paths (not just detect existence), use a DFS variant that tracks the current path array and adds it to results when the sum matches at a leaf.

Inverting (mirroring) a binary tree produces its mirror image by swapping the left and right children of every node throughout the tree.

Recursively invert the left and right subtrees first, then swap the two subtree references at the current node. The base case is a null node which returns null.

Note the order: you can swap children before or after recursing — both produce the correct result because the swap and recursion are independent operations.

Time complexity is O(n) and space is O(h) for the call stack, or O(n) for a completely skewed tree.

function invertTree(root) {
  if (!root) return null;
  [root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
  return root;
}

Destructured swap: Using array destructuring for the swap is clean and evaluates both right-side expressions before assigning — avoiding the need for a temporary variable.

This is the famous "Google interview" problem popularized on Twitter. The iterative BFS version processes nodes level by level, swapping children for each dequeued node.

A valid BST requires every node to satisfy: all nodes in its left subtree must have smaller values, and all nodes in its right subtree must have larger values — not just its direct children.

Pass a valid range (min, max) to each recursive call. The root starts with (-Infinity, Infinity). When recursing left, update the max to the current node's value. When recursing right, update the min.

A common mistake is only comparing a node to its immediate parent — this misses cases like a right subtree node being smaller than the root.

Time complexity is O(n) and space is O(h).

function isValidBST(root, min = -Infinity, max = Infinity) {
  if (!root) return true;
  if (root.val <= min || root.val >= max) return false;
  return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
}

Range propagation: Passing min/max bounds narrows the valid range at each level — this enforces the global BST property, not just the local parent-child constraint.

An alternative approach: in-order traversal of a valid BST produces a strictly increasing sequence, so validate that no in-order value is less than or equal to the previous.

The lowest common ancestor (LCA) of two nodes p and q is the deepest node that has both p and q as descendants (including the node itself).

In a standard binary tree (not necessarily BST), use recursive DFS. If the current node is p or q, return it. Recurse left and right. If both sides return non-null, the current node is the LCA.

If only one side returns non-null, both p and q are in that subtree, so bubble up that result.

This runs in O(n) time and O(h) space for the recursion stack.

function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;
  let left = lowestCommonAncestor(root.left, p, q);
  let right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left || right;
}

Both sides non-null means current is LCA: If the left subtree returns p and the right subtree returns q (or vice versa), the current node is the meeting point for both nodes.

For a BST, LCA is simpler: if both p and q are less than the current node, go left; if both are greater, go right; otherwise, the current node is the LCA.

The diameter of a binary tree is the length of the longest path between any two nodes, measured in number of edges. The path does not need to pass through the root.

At each node, the longest path through that node is the sum of the depths (heights) of its left and right subtrees. Track the global maximum across all nodes.

Use DFS that returns the depth of each subtree. Update the global max at each node with left + right, but return only 1 + max(left, right) to the parent.

This O(n) single-pass DFS avoids the O(n²) brute force that recomputes height separately for each node.

function diameter(root) {
  let max = 0;
  function depth(node) {
    if (!node) return 0;
    let l = depth(node.left), r = depth(node.right);
    max = Math.max(max, l + r);
    return 1 + Math.max(l, r);
  }
  depth(root);
  return max;
}

Update global max, return single branch: The diameter update at each node uses both branches (l + r), but the returned value uses only the longer branch to extend the path to the parent.

The diameter value is in edges (l + r), not nodes. To count in nodes, return l + r + 1 for the path through the current node.

Serialization converts a tree into a string representation that can be stored or transmitted. Deserialization reconstructs the exact tree from that string.

Use preorder traversal (root → left → right) with null markers for missing children. Each node value is separated by a delimiter, and null nodes are recorded as a special token (e.g., "null" or "#").

Deserialization uses the same preorder sequence: read values one by one from a queue and recursively build nodes, treating the null token as the signal to stop recursion.

This ensures a unique representation: the preorder + null-markers combination fully reconstructs the tree without ambiguity.

// Concept: "1,2,null,null,3,4,null,null,5,null,null"
// Preorder traversal with null markers for missing children
// Deserialize by reading values in order and recursively building nodes

Preorder with null markers: Level-order (BFS) serialization also works and is more compact, but preorder is simpler to implement and perfectly reversible.

This technique is used in database storage of hierarchical data, inter-process communication of tree structures, and deep copying complex tree objects.

The Number of Islands problem treats a binary grid as a graph where land cells ('1') are nodes and edges connect adjacent land cells (up, down, left, right).

For each unvisited land cell, run DFS or BFS to mark all connected land cells as visited. Each DFS/BFS call represents one distinct island, so increment the counter once per call.

Marking cells as '0' (or using a visited boolean array) during traversal prevents counting the same island multiple times.

Time complexity is O(m × n) and space is O(m × n) in the worst case for the DFS recursion stack.

function numIslands(grid) {
  let count = 0;
  function dfs(i, j) {
    if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] === '0') return;
    grid[i][j] = '0';
    dfs(i+1,j); dfs(i-1,j); dfs(i,j+1); dfs(i,j-1);
  }
  for (let i = 0; i < grid.length; i++)
    for (let j = 0; j < grid[0].length; j++)
      if (grid[i][j] === '1') { count++; dfs(i, j); }
  return count;
}

Mark-and-count: Overwriting visited land cells with '0' uses the grid itself as the visited array, avoiding extra O(m × n) space.

BFS (iterative with a queue) is preferred over DFS for very large grids to avoid stack overflow from deep recursion.

Zigzag level order traversal visits nodes level by level, alternating between left-to-right and right-to-left direction on each level.

Use standard BFS with a queue. For each level, process all nodes and store their values. Alternate the insertion direction: push to the end for even levels, push to the front for odd levels.

A direction flag toggled each level controls whether values are inserted normally or reversed.

Time complexity is O(n) since every node is visited once; space is O(n) for the queue and result arrays.

function zigzagLevelOrder(root) {
  if (!root) return [];
  let queue = [root], result = [], leftToRight = true;
  while (queue.length) {
    let size = queue.length, level = [];
    for (let i = 0; i < size; i++) {
      let node = queue.shift();
      if (leftToRight) level.push(node.val); else level.unshift(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
    leftToRight = !leftToRight;
  }
  return result;
}

Direction toggle: A boolean flag flipped each level avoids reversing the array afterward — inserting at front or back achieves the zigzag order in-place.

A deque-based approach can further optimize by avoiding unshift (O(n)) by appending/prepending with O(1) deque ops.

A root-to-leaf path passes through every level from the root down to a node with no children. Collecting all such paths is a classic DFS problem.

Perform DFS, maintaining the current path as an array. At each node, add its value to the path. When a leaf is reached, record a copy of the path. Backtrack by removing the node value after recursion returns.

Backtracking is essential — without it, the path array would accumulate values from sibling subtrees incorrectly.

Time complexity is O(n) for visiting all nodes; space is O(h) for the recursion stack where h is the tree height.

function binaryTreePaths(root) {
  let result = [];
  function dfs(node, path) {
    if (!node) return;
    path.push(node.val);
    if (!node.left && !node.right) result.push([...path]);
    dfs(node.left, path);
    dfs(node.right, path);
    path.pop(); // backtrack
  }
  dfs(root, []);
  return result;
}

Backtrack with pop: Adding and then removing the current node from the path restores state after returning from a subtree — the same backtracking pattern used in permutation and combination problems.

Storing [...path] (a copy) rather than path (a reference) is critical — all paths would point to the same mutating array otherwise.

Two binary trees are identical if they have the same structure and every corresponding node has the same value.

Use recursive DFS. At each step, check: both null (match), one null (mismatch), different values (mismatch). If both are non-null and values match, recurse into both left and right subtrees.

The recursion naturally handles trees of different sizes — mismatched null/non-null at any level immediately returns false.

This runs in O(min(n, m)) time where n and m are the sizes of the two trees.

function isSameTree(p, q) {
  if (!p && !q) return true;
  if (!p || !q) return false;
  if (p.val !== q.val) return false;
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

Base cases first: Check null conditions before accessing .val to avoid null reference errors — this is the standard pattern for recursive tree comparisons.

An iterative BFS version pushes corresponding node pairs onto a queue and compares them level by level — useful when stack depth is a concern.

Preorder traversal gives you the root first, then left subtree, then right subtree. Inorder gives left subtree, then root, then right subtree.

The first element of preorder is always the root. Find that root in the inorder array to determine the sizes of the left and right subtrees. Recurse with the appropriate slices of both arrays.

Using a HashMap for inorder index lookups avoids O(n) linear search per call, reducing total time from O(n²) to O(n).

This is a divide-and-conquer approach running in O(n) time with the HashMap optimization.

function buildTree(preorder, inorder) {
  let map = new Map();
  inorder.forEach((v, i) => map.set(v, i));
  let preIdx = 0;
  function build(left, right) {
    if (left > right) return null;
    let rootVal = preorder[preIdx++];
    let node = { val: rootVal, left: null, right: null };
    let idx = map.get(rootVal);
    node.left = build(left, idx - 1);
    node.right = build(idx + 1, right);
    return node;
  }
  return build(0, inorder.length - 1);
}

HashMap for O(1) root lookup: Pre-building the inorder index map eliminates the O(n) linear search per call and reduces the overall complexity to O(n).

A similar algorithm works for postorder + inorder: the last element of postorder is the root, and you build right subtree before left.

A path in a binary tree connects any node to any other node without repeating. The path can go through the root but doesn't have to — it may exist entirely within a subtree.

Use DFS where each recursive call returns the maximum "gain" from a node downward (single-branch path). At each node, compute the local maximum (left + right + node.val) and update the global maximum.

Negative branches contribute negatively, so use Math.max(0, gain) to ignore branches with negative sums.

This runs in O(n) time and O(h) space for the recursion stack.

function maxPathSum(root) {
  let max = -Infinity;
  function gain(node) {
    if (!node) return 0;
    let left = Math.max(0, gain(node.left));
    let right = Math.max(0, gain(node.right));
    max = Math.max(max, left + right + node.val);
    return node.val + Math.max(left, right);
  }
  gain(root);
  return max;
}

Gain vs path distinction: The returned value is the single-direction gain (used by the parent), while the local path value (left + right + val) is computed separately for the global maximum update.

The global max must be initialized to -Infinity, not 0, because all nodes could be negative, and the answer must include at least one node.

In a BST, inorder traversal (left → node → right) visits nodes in ascending sorted order. The kth node visited during inorder traversal is the kth smallest element.

Perform inorder DFS, decrementing a counter k each time a node is visited. When k reaches 0, record the current node's value and stop further traversal.

An iterative inorder traversal with an explicit stack is preferred for early termination without relying on exception handling or flags.

Time complexity is O(h + k) where h is the tree height; space is O(h) for the stack.

function kthSmallest(root, k) {
  let stack = [], curr = root;
  while (curr || stack.length) {
    while (curr) { stack.push(curr); curr = curr.left; }
    curr = stack.pop();
    if (--k === 0) return curr.val;
    curr = curr.right;
  }
}

Iterative inorder for early exit: The iterative version can stop immediately when k reaches 0 without visiting remaining nodes, whereas recursive DFS requires flag checks to short-circuit.

Augmenting the BST with subtree sizes (order-statistic tree) allows O(log n) kth smallest queries — useful when this query runs frequently with insertions/deletions.

A cycle in a directed graph means there exists a path from a node back to itself following directed edges. Undirected cycle detection uses a different algorithm.

Use DFS with two sets: visited (all nodes ever visited) and recursionStack (nodes in the current DFS path). A cycle is detected when a neighbor is already in the recursion stack.

After fully exploring a node, remove it from the recursion stack but keep it in visited to avoid reprocessing.

Time complexity is O(V + E) where V is vertices and E is edges.

function hasCycle(V, adj) {
  let visited = new Set(), recStack = new Set();
  function dfs(node) {
    visited.add(node); recStack.add(node);
    for (let neighbor of (adj[node] || [])) {
      if (!visited.has(neighbor) && dfs(neighbor)) return true;
      if (recStack.has(neighbor)) return true;
    }
    recStack.delete(node);
    return false;
  }
  for (let i = 0; i < V; i++)
    if (!visited.has(i) && dfs(i)) return true;
  return false;
}

Recursion stack tracks the current path: A back edge (neighbor in recStack) means there is a path from the neighbor to the current node, forming a cycle in the directed graph.

For undirected graphs, simpler logic applies: if a neighbor is already visited and is not the parent node, a cycle exists.

Topological sort orders vertices of a DAG such that for every directed edge u → v, u comes before v. It is used in task scheduling, dependency resolution, and build systems.

DFS-based approach: perform DFS on all nodes; when a node is fully processed (all descendants visited), push it to a stack. The stack's reverse order (or popping order) is the topological order.

Kahn's algorithm (BFS-based) processes nodes with in-degree 0 first. It naturally detects cycles if not all nodes are processed.

Both run in O(V + E) time.

function topoSort(V, adj) {
  let visited = new Set(), stack = [];
  function dfs(node) {
    visited.add(node);
    for (let nb of (adj[node] || [])) if (!visited.has(nb)) dfs(nb);
    stack.push(node);
  }
  for (let i = 0; i < V; i++) if (!visited.has(i)) dfs(i);
  return stack.reverse();
}

Post-order push: Pushing a node after all its descendants are processed ensures it appears before all nodes that depend on it when the stack is reversed.

Kahn's algorithm is preferred for cycle detection since nodes with a cycle never reach in-degree 0 and remain unprocessed — the count of processed nodes will be less than V.

Dijkstra's algorithm finds the shortest path from a source node to all other nodes in a graph with non-negative edge weights.

Use a priority queue (min-heap). Initialize all distances as Infinity, set the source to 0. Repeatedly extract the node with the smallest current distance and relax its neighbors.

Relaxation: if dist[u] + weight(u, v) < dist[v], update dist[v] and push to the priority queue.

With a binary heap, time complexity is O((V + E) log V). Without a heap, it is O(V²) but simpler to implement.

function dijkstra(graph, src) {
  let dist = {}, visited = new Set();
  for (let node in graph) dist[node] = Infinity;
  dist[src] = 0;
  let pq = [[0, src]]; // [distance, node]
  while (pq.length) {
    pq.sort((a, b) => a[0] - b[0]);
    let [d, u] = pq.shift();
    if (visited.has(u)) continue;
    visited.add(u);
    for (let [v, w] of (graph[u] || [])) {
      if (d + w < dist[v]) { dist[v] = d + w; pq.push([dist[v], v]); }
    }
  }
  return dist;
}

Greedy shortest path: Always processing the node with the smallest known distance guarantees that when a node is finalized (added to visited), its distance is optimal.

Dijkstra fails with negative edge weights — use Bellman-Ford instead which handles negative weights in O(VE) time.

A bipartite graph can have its vertices divided into two sets such that every edge connects a vertex in one set to a vertex in the other. Equivalently, a graph is bipartite if and only if it contains no odd-length cycles.

Use BFS or DFS to color the graph with two colors. Start with any node as color 0. For each neighbor, assign the opposite color. If a neighbor already has the same color as the current node, the graph is not bipartite.

This check must be performed for all connected components (in case the graph is disconnected).

Time complexity is O(V + E).

function isBipartite(graph) {
  let color = Array(graph.length).fill(-1);
  for (let start = 0; start < graph.length; start++) {
    if (color[start] !== -1) continue;
    let queue = [start]; color[start] = 0;
    while (queue.length) {
      let node = queue.shift();
      for (let nb of graph[node]) {
        if (color[nb] === -1) { color[nb] = 1 - color[node]; queue.push(nb); }
        else if (color[nb] === color[node]) return false;
      }
    }
  }
  return true;
}

Two-coloring check: Any node with the same color as its neighbor proves an odd-length cycle exists — bipartite and odd cycles are mutually exclusive.

Bipartite checking is used in matching problems (e.g., job assignments), social network analysis, and scheduling with conflict constraints.

In an undirected graph, a connected component is a maximal set of nodes where every node is reachable from every other node via edges.

Use DFS or BFS starting from each unvisited node. Each new DFS/BFS call from an unvisited starting node represents a new connected component.

Union-Find (Disjoint Set Union) is an alternative that efficiently handles dynamic edge additions with near-O(1) per operation.

Time complexity is O(V + E) with DFS/BFS.

function countComponents(n, edges) {
  let adj = Array.from({length: n}, () => []);
  for (let [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
  let visited = new Set(), count = 0;
  function dfs(node) {
    visited.add(node);
    for (let nb of adj[node]) if (!visited.has(nb)) dfs(nb);
  }
  for (let i = 0; i < n; i++) { if (!visited.has(i)) { count++; dfs(i); } }
  return count;
}

One DFS per component: Each unvisited node that triggers a new DFS call is in an unexplored component — the count of such calls equals the number of components.

Union-Find is preferred when you need to dynamically count components as edges are added, since it handles this incrementally with path compression and union by rank.

Word Ladder asks for the shortest sequence of words from a start word to an end word where each step changes exactly one letter and every intermediate word must be in a dictionary.

Use BFS to find the shortest path. From each word, generate all possible one-letter variations and check if they exist in the word set. Visit each word at most once.

Removing words from the set as they are visited prevents revisiting and ensures each word is on the shortest path only.

Time complexity is O(M² × N) where M is word length and N is dictionary size; generating variations is the bottleneck.

function ladderLength(beginWord, endWord, wordList) {
  let set = new Set(wordList), queue = [[beginWord, 1]];
  while (queue.length) {
    let [word, steps] = queue.shift();
    for (let i = 0; i < word.length; i++) {
      for (let c = 97; c <= 122; c++) {
        let next = word.slice(0, i) + String.fromCharCode(c) + word.slice(i+1);
        if (next === endWord) return steps + 1;
        if (set.has(next)) { set.delete(next); queue.push([next, steps+1]); }
      }
    }
  }
  return 0;
}

BFS for shortest path: BFS guarantees the minimum number of steps since it explores all paths of length k before any path of length k+1.

Bidirectional BFS from both start and end can halve the search space, offering significant speedup for large dictionaries.

A height-balanced binary tree has the property that for every node, the heights of its left and right subtrees differ by at most 1.

Use a post-order DFS that returns the height of each subtree. If any subtree is unbalanced (height -1 as sentinel), propagate -1 upward without further computation.

This runs in O(n) with a single pass — the naive approach that recomputes height separately is O(n²).

The -1 sentinel value signals an imbalance; the root returns -1 if any subtree is imbalanced, otherwise returns its actual height.

function isBalanced(root) {
  function height(node) {
    if (!node) return 0;
    let l = height(node.left), r = height(node.right);
    if (l === -1 || r === -1 || Math.abs(l - r) > 1) return -1;
    return 1 + Math.max(l, r);
  }
  return height(root) !== -1;
}

-1 sentinel for early termination: Returning -1 from an unbalanced subtree short-circuits all ancestor computations without needing a separate flag variable.

AVL trees maintain this balance invariant on every insertion/deletion through rotations, guaranteeing O(log n) for all operations.

The ancestors of a target node are all nodes on the path from the root to that target node, excluding the target itself.

Use DFS. At each node, recurse into left and right subtrees. If either subtree finds the target, include the current node in the ancestors path and return true to propagate up.

The path is built during the return phase of recursion — nodes are added as the successful path unwinds upward through the call stack.

This runs in O(n) time and O(h) space for the recursion stack where h is the tree height.

function findAncestors(root, target) {
  let ancestors = [];
  function dfs(node) {
    if (!node) return false;
    if (node.val === target) return true;
    if (dfs(node.left) || dfs(node.right)) {
      ancestors.push(node.val);
      return true;
    }
    return false;
  }
  dfs(root);
  return ancestors.reverse(); // root-to-parent order
}

Return-phase accumulation: Nodes are added to the ancestor list as the DFS unwinds upward — naturally giving them in reverse order (leaf's parent first to root last).

This same DFS pattern is used in LCA (Lowest Common Ancestor) problems, where you check whether both left and right subtrees return true for different targets.