208. Implement Trie (Prefix Tree) - Detailed Explanation

Problem statement

Implement the Trie class:

• Trie() Initializes the trie object.
• void insert(String word) Inserts the string word into the trie.
• boolean search(String word) Returns true if the exact string word is in the trie (i.e., was previously inserted), or false otherwise.
• boolean startsWith(String prefix) Returns true if there is any previously inserted string that starts with the given prefix, or false otherwise.

Examples

Input
["Trie","insert","search","search","startsWith","insert","search"]
[[],       ["apple"],["apple"],["app"],    ["app"],      ["app"],["app"]]

Output
[null,     null,     true,     false,       true,        null,    true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false (only prefix "app" exists)
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app");     // returns true

Constraints

• 1 ≤ word.length, prefix.length ≤ 2000
• word and prefix consist only of lowercase English letters.
• At most 3·10⁴ calls in total will be made to insert, search, and startsWith.

Approach

This question names its own pattern: the Trie, also called a prefix tree. A trie is a tree in which the path from the root to a node spells a string. Every stored word is therefore a route through the tree rather than a value sitting in a slot, and words that share a prefix share that part of the route. The structure is one of the standard data structures behind the recurring coding interview patterns, and it is the answer whenever an interviewer asks about prefixes rather than whole keys.

A hash set looks tempting here, and it does answer search in O(1) on average. It cannot answer startsWith without inspecting every key it holds. The trie turns that query into a walk of at most m steps, where m is the length of the prefix, which is the whole reason to build one.

Trie node structure

Each node holds:

• An array (or map) of up to 26 child pointers, one for each lowercase letter.
• A boolean flag isEnd indicating whether a word ends at this node.

The isEnd flag is what separates a stored word from a passing prefix. Inserting "apple" creates five nodes and sets isEnd only on the last one. So search("app") reaches a real node and still returns false, because that node is only a waypoint, while startsWith("app") returns true from the same node. Insert "app" later and the flag on that existing node flips to true, with no new nodes allocated.

Operations

insert(word)

1. Start at the root node.
2. For each character c in word:
   • Compute its index i = c - 'a'.
   • If node.children[i] is null, create a new TrieNode.
   • Move node = node.children[i].
3. After the last character, mark node.isEnd = true.

search(word)

1. Traverse exactly as in insert, but if at any step node.children[i] is null, return false.
2. After processing all chars, return node.isEnd.

startsWith(prefix)

1. Traverse as in search, but do not check isEnd.
2. If you complete the traversal without hitting null, return true.

All three operations are the same walk over one string, differing only in what they do when a child link is missing and in what they report at the end. Write the walk once as a private helper that returns the node reached or null, then express search and startsWith on top of it. Grokking the Coding Interview builds the class in that order in its Implement Trie lesson, which is where the problem and the rest of the trie pattern are taught.

Complexity analysis

• Time: O(m) per operation (m = length of word or prefix).
• Space: In the worst case, O(N·L) for storing all inserted words (N words of average length L), since each character may create a new node.

Python code

Java code