Trees And Hierarchical Structures
Asked of: Software Engineer
Last updated

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— processlevel_sizenodes per depth; supports right-side view, zigzag traversal, and shortest-by-depth reasoning inO(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 areO(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 - 1parent edges forn > 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 isO(w)for BFS width,O(h)recursion depth, orO(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.
Featured in interview prep guides
Practice questions
- Determine Reporting RelationshipsGoogle · Software Engineer · Technical Screen · none
- Validate parent array forms a treeGoogle · Software Engineer · Technical Screen · medium
- Find mode in a trinary search treeGoogle · Software Engineer · Technical Screen · medium
- Find right-side view of binary treeGoogle · Software Engineer · Technical Screen · easy
- Solve tree, graph, sliding-window problemsGoogle · Software Engineer · Technical Screen · Medium
- Implement zigzag level-order traversalGoogle · Software Engineer · Technical Screen · Medium
- Delete a Node From a Search TreeGoogle · Software Engineer · Onsite · hard
Related concepts
- Trees, Tries, and Hierarchical DataCoding & Algorithms
- Tree Traversal And Hierarchical StructuresCoding & Algorithms
- Tree And Linked Structure AlgorithmsCoding & Algorithms
- Trees, Recursion, And BST TraversalCoding & Algorithms
- Trees, Linked Lists, And Pointer AlgorithmsCoding & Algorithms
- Binary Tree Traversals, Vertical Order, And ViewsCoding & Algorithms