Implement Trie (Prefix Tree) - Video Solutions

Problem Overview: Design a Trie (Prefix Tree) that supports three operations: insert(word), search(word), and startsWith(prefix). Each operation must efficiently process strings by sharing common prefixes across stored words.

Approach 1: Native Trie with Fixed Children Array (O(L) time per operation)

This approach builds a classic Trie where each node stores an array of size 26 for lowercase English letters. During insert, iterate through the characters of the word and create nodes if they don't exist. For search and startsWith, traverse the tree following character indexes. The key insight is prefix sharing: multiple words reuse the same nodes until their paths diverge. Each operation runs in O(L) time where L is the word length, because you process one character at a time. Space complexity is O(N * L) in the worst case for storing all characters across inserted words. This implementation is extremely fast due to constant-time array access.

Approach 2: Trie Using Hash Maps (O(L) time per operation)

Instead of allocating a fixed array of 26 children, each node stores a dynamic map (hash table) from character to child node. While inserting a word, check the map for the next character and create a node only when necessary. search and startsWith follow the same traversal logic but rely on hash lookups. The time complexity remains O(L) per operation, but space becomes more efficient for sparse datasets because nodes only store existing edges. The tradeoff is slightly slower lookups due to hashing compared to array indexing. This approach combines concepts from hash tables and tries and is easier to generalize when the character set is large.

Both approaches exploit prefix compression: shared prefixes reduce redundant storage and allow quick prefix checks. This makes Tries particularly effective for autocomplete systems, dictionary lookups, and prefix-based search features.

Recommended for interviews: The fixed-array Trie is the implementation most interviewers expect. It demonstrates clear understanding of data structure design and delivers predictable O(L) operations with minimal overhead. The hash-map variant is useful when the character set is large or memory usage matters. Showing both approaches signals strong understanding of tradeoffs.