Trees And Hierarchical Structures

What's being tested

Tree traversal and hierarchical invariant reasoning: you need to move confidently between recursive DFS, iterative BFS, parent-pointer arrays, and search-tree variants. Interviewers are probing whether you can derive the traversal order, maintain per-level/per-node state, prove correctness, and give tight O(n) time / space bounds.

Patterns & templates

• Level-order BFS with queue — process level_size nodes per depth; supports right-side view, zigzag traversal, and shortest-by-depth reasoning in O(n) time.

• DFS by depth using dfs(node, depth) — record first or last node seen per depth; preorder right-first solves right-side view cleanly.

• Alternating level output — for zigzag, append normally then reverse, or use deque.appendleft; both are O(n), but avoid repeated front inserts into arrays.

• Search-tree traversal — exploit BST/trinary ordering when useful, but mode finding still needs frequency tracking; handle duplicate keys and "middle/equal" child conventions explicitly.

• Parent-array validation — a valid tree has exactly one root, no cycles, all nodes connected, and exactly n - 1 parent edges for n > 0.

• Cycle detection — use DFS colors (WHITE/GRAY/BLACK) or Union-Find; parent-pointer graphs often fail via self-parent, multi-root, or disconnected components.

• Complexity discipline — most solutions should be O(n) time; auxiliary space is O(w) for BFS width, O(h) recursion depth, or O(n) for visited/state arrays.

Common pitfalls

• Pitfall: Treating level-order traversal as “visit until queue empty” without freezing level_size, which mixes depths and breaks right-side or zigzag output.

• Pitfall: Assuming “one root” is enough for a parent array; you must also prove no cycles and full connectivity.

• Pitfall: Ignoring recursion depth on skewed trees; mention iterative traversal or stack limits when h ≈ n.

Practice these

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