Trees, Tries, and Hierarchical Data

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 n nodes are connected in O(n).

• DFS/BFS traversal — use visited and visiting states for cycle detection; recursion is concise but iterative stacks avoid depth overflow.

• Union-Find for hierarchy validation — find/union catches cycles in near-constant amortized time, $O(\alpha(n))$, but still check root count.

• Prefix filtering — word.startswith(prefix) over an array is O(total_chars); define case sensitivity, duplicate behavior, and empty-prefix semantics upfront.

• Trie template — insert, searchPrefix, and subtree collection cost O(L + output); store children, 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).