Implement Trie (Prefix Tree)

Implement Trie (Prefix Tree)

What is this problem about?

The Implement Trie (Prefix Tree) interview question is one of the most fundamental data structure design tasks. You need to implement a "Prefix Tree" or "Trie" that supports three operations:

1. insert(word): Adds a word to the tree.
2. search(word): Returns true if the exact word exists.
3. startsWith(prefix): Returns true if any word in the Trie starts with the given prefix.

Why is this asked in interviews?

Tries are ubiquitous in search engines, IP routing, and auto-complete systems. This question is a favorite at Google, Meta, and Amazon because it tests whether you understand how to share prefixes to save space and speed up searches. It also evaluates your skill in designing custom recursive structures and choosing between a Map or a fixed-size array for child pointers.

Algorithmic pattern used

The problem uses the Trie design pattern.

• Node: Each node contains an array of 26 pointers (one for each lowercase letter) or a Hash Map. It also includes a boolean flag isEndOfWord.
• Insert: Traverse the tree character by character. If a child for the next character doesn't exist, create it. At the end of the word, set isEndOfWord = true.
• Search: Traverse the path. If you hit a null pointer, the word isn't there. If you finish the path, check if isEndOfWord is true.
• StartsWith: Similar to search, but you don't care about the isEndOfWord flag at the end.

Example explanation

1. insert("car"): root -> c -> a -> r (end).
2. insert("cat"): root -> c -> a -> t (end). (The "ca" prefix is shared).
3. search("ca"): Follows c -> a. Ends at 'a', but isEndOfWord is false. Returns false.
4. startsWith("ca"): Follows c -> a. Path exists. Returns true.

Common mistakes candidates make

• Array size: Using a fixed size of 26 without clarifying if only lowercase English letters are allowed.
• Search vs. StartsWith: Confusion between the two logic paths (forgetting the end-of-word check in search).
• Root Node: Not properly initializing the root node or trying to store a character in the root itself.

Interview preparation tip

Be ready to discuss Space Complexity. A Trie can consume a lot of memory because of the null pointers. Interviewers may ask how to optimize this (e.g., using a Hash Map for children instead of an array, or using a "Ternary Search Tree").