Tree Traversal And Hierarchical Structures

What's being tested

Tree traversal over binary and N-ary hierarchies: choosing DFS vs BFS, preserving ordering, and attaching metadata like depth, column, or path position. Interviewers probe whether you can convert a structural requirement—vertical order, boundary, kth value, indentation—into a clean traversal invariant with correct edge-case handling.

Patterns & templates

• DFS with depth state — dfs(node, depth) gives indentation, boundary levels, or recursive formatting; O(n) time, O(h) call stack.

• BFS with coordinates — queue (node, row, col) for vertical traversal; sort by col, then row, then value if required.

• In-order traversal for BSTs — left -> node -> right yields sorted order; stop after k visits for O(h + k) time.

• Boundary traversal — split into left boundary, leaves, right boundary; avoid duplicating root or leaf nodes across phases.

• N-ary ordered children — child index matters; first child often defines left view/boundary, last child defines right view/boundary.

• Iterative stack template — use (node, depth, state) when recursion depth may exceed limits; preserves explicit traversal control.

• Complexity discipline — most solutions should be O(n) time; vertical traversal may add O(n log n) sorting unless grouping order is maintained.

Common pitfalls

Pitfall: Treating vertical traversal as simple BFS without tie-breaking; equal column and row cases must be ordered exactly as specified.

Pitfall: Duplicating nodes in boundary problems, especially when a boundary node is also a leaf.

Pitfall: Forgetting degenerate trees: empty tree, single node, linked-list-shaped tree, or N-ary nodes with zero children.

Practice these

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