Watch how a Trie powers autocomplete: traverse the prefix path then DFS-collect all matching words. O(L + K) where K = number of completions.
Autocomplete is one of the most practical Trie applications. Pick a prefix and watch the algorithm walk the prefix path, then DFS-collect every word reachable from that point.
Phase 1: walk the prefix char-by-char (O(L)). If any char is missing, return []. Phase 2: DFS from the prefix endpoint. Every node with isEnd=true is a valid completion.
Traverse the trie one character at a time. If a character is missing, return [] immediately. Otherwise, keep moving down.
From the prefix endpoint, run DFS. Every node with isEnd=true contributes a word. The full word is reconstructed by accumulating characters along the path.
O(L + K) where L = prefix length, K = total characters in all completions. Space: O(K) for storing results.
L = prefix length, K = total characters in all completions. Autocomplete is why Tries are preferred over hash maps for search boxes and IDEs.