Trees, Graphs, And Recursive Traversal

What's being tested

These problems test recursive traversal and iterative stack/queue equivalents across nested lists, trees, grids, and graphs. You must model relationships correctly, track depth or distance, avoid revisiting nodes, and choose DFS, BFS, or BST-specific traversal based on the required result.

Patterns & templates

• Nested-list depth aggregation — compute maximum depth first, then apply inverse-depth weights; use recursion or an explicit stack when nesting may exceed call-stack limits.

• DFS connected components — scan every grid cell, launch DFS on unvisited land, and mark during traversal; runs in O(rows × cols) time and O(rows × cols) space.

• BFS shortest path — for unweighted graphs, process nodes by levels with a queue; the first visit gives fewest edges, including distance 0 for identical endpoints.

• Visited-state design — mutate the grid, use a boolean matrix, or maintain a hash set; distinguish “seen” from “fully processed” for directed graphs.

• DAG distance computation — topologically order vertices, initialize source distance to 0, and relax outgoing edges; unreachable targets remain -1.

• Canonical island shapes — record coordinates relative to an anchor, then normalize or serialize each shape; translation-equivalent islands share one representation.

• BST closest values — exploit inorder sortedness with predecessor/successor stacks, or maintain a bounded heap; compare absolute differences and handle duplicates consistently.

Common pitfalls

Pitfall: Treating diagonal grid cells as adjacent when the contract specifies four-directional movement, or vice versa.

Pitfall: Using DFS for shortest unweighted distance without tracking levels; DFS finds a path, not necessarily the fewest edges.

Pitfall: Forgetting cycles, duplicate values, empty inputs, disconnected components, or recursion-depth limits in skewed trees and deeply nested lists.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.