Tree And Graph Modeling Algorithms
Asked of: Software Engineer
Last updated

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; return1 + 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 -> Bhas multiplicative rater; path value is product of edge weights. -
Max-product path can use modified
Dijkstrawith 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 beO((V + E) log V)with heap-based best-path search.
Common pitfalls
Pitfall: Mixing height definitions. Clarify whether a single CEO node has height
0edges or1layer 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
0unless the prompt defines that behavior.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
Related concepts
- Graph Traversal And Shortest PathsCoding & Algorithms
- Graph Algorithms, Dependency Resolution And ConnectivityCoding & Algorithms
- Graph Search And Weighted PathsCoding & Algorithms
- Shortest Path And Graph TraversalCoding & Algorithms
- Tree And Graph ConnectivityCoding & Algorithms
- DFS/BFS Tree, Graph, And Grid TraversalCoding & Algorithms