Tree And Graph Connectivity

What's being tested

Tests tree dynamic programming for aggregating root-to-leaf costs and graph connectivity for grouping items under transitive similarity. Interviewers are checking whether you can map a story problem to DFS, postorder aggregation, or Union-Find, then reason cleanly about correctness and O(n) or O(n^2) bounds.

Patterns & templates

• Postorder tree DP — compute child path sums first; return nodeCost + max(left, right) while accumulating balancing work.

• Path equalization — when two child subtrees differ, minimum added cost is abs(leftSum - rightSum); never decrement, only raise the cheaper side.

• DFS over adjacency matrix — scan each unvisited node, run dfs(i) over all j where matrix[i][j] == 1; total O(n^2).

• Union-Find / DSU — find, union, path compression, union by rank; ideal for pairwise similarity components and repeated merges.

• Connected components — count roots after unions or count DFS launches; similarity is treated as transitive even if not directly connected.

• Indexing discipline — tree arrays may be 1-indexed or 0-indexed; binary children are often 2*i+1, 2*i+2 or 2*i, 2*i+1.

• Complexity statement — tree balancing is O(n) time, O(h) recursion space; adjacency matrix connectivity is O(n^2) time, O(n) space.

Common pitfalls

Pitfall: Equalizing every root-to-leaf path globally first is overcomplicated; local subtree balancing in postorder gives the minimum increments.

Pitfall: Treating photo similarity as only direct pairs misses transitive groups; use connected components, not pair counting.

Pitfall: Forgetting recursion depth limits on skewed trees; mention iterative DFS or stack-size concerns when n can be large.

Practice these

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