Coding

Trees & Graphs Coding Questions

Q: DFS vs BFS — when to use each?

DFS: path finding, cycle detection, topological sort, exploring all paths, tree serialization. Uses a stack (or recursion). BFS: shortest path in unweighted graph, level-order traversal, minimum steps problems. Uses a queue. BFS is safer for very deep trees (avoids stack overflow that DFS recursion causes).

Q: What tree traversals should I know?

In-order (left, root, right) — produces sorted order for BST. Pre-order (root, left, right) — useful for tree serialization and copy. Post-order (left, right, root) — useful for deletion and computing subtree properties. Level-order (BFS) — useful for anything level-based. Know iterative implementations of all four.

Q: How do I handle cycles in graph problems?

For undirected graphs: track visited nodes in a set; skip if already visited. For directed graphs: 3-state DFS (unvisited/in-progress/done) to detect back edges (cycles). Union-Find is also effective for undirected cycle detection with near O(1) per operation.

Q: What is Union-Find and when should I use it?

Union-Find (Disjoint Set Union) efficiently groups elements into sets and checks if two elements are in the same set. Operations: find(x) returns root of x's set, union(x, y) merges their sets. With path compression and union by rank, both are near O(1). Use for: connected components, cycle detection in undirected graphs, Kruskal's MST algorithm.

Trees and graphs are the most heavily tested data structures in coding interviews at top companies. These problems require mastering DFS, BFS, recursion, and key tree properties.

Practice with AI Feedback — Free AI Mock Interview

Sample Questions & Strong Answers

Maximum Depth of Binary Tree.

Recursive DFS: maxDepth(node) = 1 + max(maxDepth(left), maxDepth(right)). Base case: null returns 0. Iterative: BFS level-order traversal, count levels. Time O(n), Space O(h) where h is tree height.

💡

Pro tip: Know both recursive and iterative (BFS) solutions. BFS is cleaner for level-based problems. Amazon, Google, Meta warm-up.

Invert Binary Tree.

Recursive: swap left and right children, then recurse into both. Base case: null returns null. Iterative: use a queue (BFS) or stack (DFS). Time O(n), Space O(h).

💡

Pro tip: This problem is famous because an engineer who 'couldn't invert a binary tree' went viral. Know it cold. Apple, Google.

Validate Binary Search Tree.

Pass min/max bounds down recursively. At each node: value must be > min and < max. Left subtree passes (min, node.val), right passes (node.val, max). Base bounds: (−∞, +∞). In-order traversal must be strictly increasing — another valid check.

💡

Pro tip: Don't just check left < node < right — that misses the case where a right subtree has a node less than a distant ancestor. Amazon, Google, Meta.

Lowest Common Ancestor of a Binary Tree.

Recursive: if root is p or q, return root. Recurse left and right. If both return non-null, root is the LCA. If only one returns non-null, return that one. Time O(n), Space O(h).

💡

Pro tip: For BST variant: use BST property to navigate. For general tree: this single-pass recursive approach is optimal. Meta, Google.

Binary Tree Level Order Traversal (BFS).

Use a queue. For each level: record queue length, dequeue that many nodes (collect values), enqueue their children. Append level's values to result. Time O(n), Space O(n) (max queue size = widest level).

💡

Pro tip: The 'snapshot queue length per level' trick is the key to clean level-order traversal. Amazon, Google, Microsoft.

Number of Islands — count connected components of '1's in a grid.

Iterate grid. When '1' is found, increment count and DFS/BFS to mark all connected '1's as visited (set to '0'). Time O(m×n), Space O(m×n) for recursion stack. Also solvable with Union-Find.

💡

Pro tip: DFS is simpler to code; BFS avoids stack overflow on large grids. Mention both trade-offs. Amazon, Meta, Google — extremely common.

Course Schedule — detect cycle in directed graph (topological sort).

Build adjacency list. DFS with 3 states: unvisited (0), in-progress (1), done (2). If DFS reaches an in-progress node, cycle exists. Alternatively, Kahn's algorithm (BFS topological sort): if not all nodes are processed, cycle exists. Time O(V+E).

💡

Pro tip: The 3-state DFS (unvisited/visiting/visited) is the clean cycle detection approach. Google, Amazon — medium-hard.

Serialize and Deserialize Binary Tree.

Serialize: pre-order DFS, write 'null' for missing nodes. Deserialize: split by delimiter, use a queue and recursive pre-order construction. Time O(n), Space O(n). The pre-order format uniquely encodes the tree structure.

💡

Pro tip: This tests your ability to design a protocol. Explain your encoding choice before coding. Meta, Google — hard, but commonly asked at senior level.

Binary Tree Maximum Path Sum.

For each node, compute the max gain if a path passes through it: gain = node.val + max(0, leftGain) + max(0, rightGain). Update global max. Return node.val + max(0, leftGain, rightGain) to parent (path can only go one direction upward). Time O(n).

💡

Pro tip: The two computations are distinct: the answer (passing through node) vs. what you return to parent (must be linear). Amazon, Meta, Google — hard.

Clone Graph — deep copy an undirected graph.

DFS or BFS with a hash map mapping original nodes to clones. For each neighbor of an original node: if not in map, create clone and recurse. Attach cloned neighbors to cloned node. Time O(V+E), Space O(V).

💡

Pro tip: The hash map is both visited set and clone registry — elegant dual-purpose. Meta, Google.

Word Ladder — minimum word transformations from begin to end.

BFS from beginWord. At each step, try changing each character to a–z and check if it's in the wordList (use a set for O(1)). BFS guarantees shortest path. Remove words from set as visited. Time O(m² × n) where m=word length, n=list size.

💡

Pro tip: Remove words from the set when visited (don't just mark visited) — prevents revisiting and reduces memory. Google, Amazon — hard.

Diameter of Binary Tree — longest path between any two nodes.

DFS: for each node compute left depth + right depth (this is the diameter through that node). Track max across all nodes. Return max(leftDepth, rightDepth) + 1 to parent. Time O(n), Space O(h).

💡

Pro tip: The diameter doesn't have to pass through the root — that's the critical insight requiring DFS everywhere. Google, Amazon.

Pacific Atlantic Water Flow — cells that can flow to both oceans.

BFS/DFS from Pacific border cells and Atlantic border cells separately, marking reachable cells. Intersection of both sets is the answer. Time O(m×n), Space O(m×n). Reverse the flow direction: water 'flows up' from ocean borders.

💡

Pro tip: Reversing flow direction (from ocean inward instead of cell outward) is the key insight for efficiency. Google, Amazon.

Graph Valid Tree — check if undirected graph with n nodes and edges is a tree.

A tree has exactly n−1 edges and is connected. Check both conditions: 1) edges.length !== n−1 → false. 2) DFS/BFS from node 0, count visited nodes — must reach all n. Union-Find is also clean here. Time O(V+E).

💡

Pro tip: Two conditions must hold: n−1 edges AND connected. Missing either makes it not a tree. Google, Amazon.

Construct Binary Tree from Preorder and Inorder Traversal.

First element of preorder is always root. Find root in inorder — elements left are left subtree, right are right subtree. Recurse with corresponding subarrays. Use a hash map for O(1) inorder lookup. Time O(n), Space O(n).

💡

Pro tip: The hash map for inorder lookup reduces time from O(n²) to O(n). Amazon, Meta — medium-hard.

Expert tips

Master DFS and BFS implementations from scratch — interviews rarely allow you to look these up.

For tree problems, always consider: can this be solved with a single DFS pass vs. multiple passes?

Graph problems often reduce to tree problems — detect if it's a tree first (n−1 edges, connected).

Topological sort (Kahn's BFS or DFS with 3 states) solves all dependency/ordering/cycle detection problems.