Trees, Tries, and Hierarchical Data
Asked of: Software Engineer
Last updated
What's being tested
Trees, tries, and hierarchical data questions test whether you can model parent-child structure, preserve invariants, and choose the right index for prefix or lexicographic queries. Interviewers look for clean traversal logic, precise edge-case handling, and complexity-aware tradeoffs between scanning, sorting, hashing, and trie-based indexing.
Patterns & templates
-
Parent-array validation — count exactly one root, reject invalid parent indices, detect cycles, and verify all
nnodes are connected inO(n). -
DFS/BFS traversal — use
visitedandvisitingstates for cycle detection; recursion is concise but iterative stacks avoid depth overflow. -
Union-Find for hierarchy validation —
find/unioncatches cycles in near-constant amortized time, , but still check root count. -
Prefix filtering —
word.startswith(prefix)over an array isO(total_chars); define case sensitivity, duplicate behavior, and empty-prefix semantics upfront. -
Trie template —
insert,searchPrefix, and subtree collection costO(L + output); storechildren,isWord, and optional frequency/top-k metadata. -
Augmented trie autocomplete — cache top candidates per node for
O(L + k)query time; updates become more complex, especially delete/frequency changes. -
Lexicographic range queries — sorted arrays or balanced trees answer
[lo, hi]with binary search plus scan:O(log n + m).
Common pitfalls
Pitfall: Treating “one root” as sufficient for a valid tree; disconnected components and cycles can still exist.
Pitfall: Building a trie for tiny static input without justifying the extra memory versus a sorted list or linear scan.
Pitfall: Forgetting output size in complexity; returning 10,000 matching words cannot be faster than
O(output).
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Practice questions
- Return dictionary words matching a prefixGoogle · Software Engineer · Technical Screen · medium
- 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
- Design lexicographic range query word storeGoogle · Software Engineer · Onsite · hard
- Design autocomplete with TrieGoogle · Software Engineer · Onsite · Medium
- Implement zigzag level-order traversalGoogle · Software Engineer · Technical Screen · Medium
Related concepts
- Trees And Hierarchical StructuresCoding & Algorithms
- Tree Traversal And Hierarchical StructuresCoding & Algorithms
- Trees, Recursion, And BST TraversalCoding & Algorithms
- Tree And Linked Structure AlgorithmsCoding & Algorithms
- Trees, Linked Lists, And Pointer AlgorithmsCoding & Algorithms
- Binary Tree Traversals, Vertical Order, And ViewsCoding & Algorithms