Tree and graph task patterns

Tree and graph tasks start with modeling. Trees usually have implicit child links and no cycles; graphs often require building adjacency and tracking visited nodes. DFS is natural for components and backtracking; BFS is natural for shortest unweighted distance and level order.

Trade-off: compare time, memory, and implementation complexity before committing to a structure or pattern.

On interviews: Interviewers expect you to describe traversal order, what state is carried, and why the algorithm terminates in cyclic inputs.

Common pitfalls: A tree solution can break when the hidden input is actually a graph with shared nodes. Parent pointers can cause revisiting unless you exclude the source of traversal.

Checklist:

• Model adjacency.
• Choose DFS or BFS.
• Carry state explicitly.
• Use visited for cycles.