Tree And Graph Modeling Algorithms

What's being tested

These problems test tree traversal and graph path modeling: turning business-shaped relationships like reporting lines or currency markets into nodes, edges, weights, and constraints. Interviewers are probing whether you can choose the right traversal, compute structural properties efficiently, and reason about optimization over paths or subtrees.

Patterns & templates

• DFS postorder on rooted trees computes subtree height in O(n) time; return 1 + max(child_heights) and handle leaf height consistently.

• BFS level-order traversal is ideal for reporting layers; queue (node, depth) pairs and track max depth without recursion-stack risk.

• Subtree rerooting / promotion simulation needs cached subtree heights; avoid recomputing depth from scratch after every hypothetical move.

• Directed weighted graph modeling for currencies: edge A -> B has multiplicative rate r; path value is product of edge weights.

• Max-product path can use modified Dijkstra with priority queue maximizing amount; equivalent to shortest path on -log(rate) weights.

• Cycle handling is mandatory in graphs; use visited/best-known amount maps, and clarify whether arbitrage cycles are allowed.

• Complexity target: tree traversals should be O(n); graph conversion should be O((V + E) log V) with heap-based best-path search.

Common pitfalls

Pitfall: Mixing height definitions. Clarify whether a single CEO node has height 0 edges or 1 layer before coding.

Pitfall: Treating currency conversion as unweighted BFS. Fewest hops is not necessarily the best conversion rate.

Pitfall: Forgetting disconnected components or missing paths. Return impossible explicitly, not 0 unless the prompt defines that behavior.

Practice these

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