Implement Trie Prefix Tree LeetCode 208

LeetCode 208 — Implement Trie (Prefix Tree) — asks you to implement a Trie class with three methods: insert(word) adds a word to the trie, search(word) returns true if the word exists in the trie, and startsWith(prefix) returns true if any word in the trie starts with the given prefix.

A trie is a tree-like data structure that stores strings character by character. Each node represents a character, and paths from root to marked nodes form stored words. Unlike hash sets, tries support efficient prefix queries.

Tries are fundamental in autocomplete systems, spell checkers, IP routing tables, and word games. This problem tests your ability to design a tree-based data structure from scratch — a common interview task at Google, Amazon, and Microsoft.

Each TrieNode has two fields: children (a map from character to child TrieNode) and isEnd (a boolean indicating whether this node marks the end of a stored word). The root is an empty TrieNode.

For lowercase English letters, children can be a dictionary/HashMap or a fixed-size array of 26 entries. The array approach uses more memory but offers O(1) child lookup. The map approach is more space-efficient for sparse tries.

The isEnd flag distinguishes complete words from prefixes. For example, if "apple" is inserted, nodes a→p→p→l→e exist. Only the "e" node has isEnd = true. The prefix "app" traverses a→p→p but that "p" node has isEnd = false.

Start at the root. For each character in the word: if the current node has no child for this character, create a new TrieNode and add it as a child. Move to the child node. After processing all characters, set isEnd = true on the final node.

Insert runs in O(m) time where m is the word length. Each character requires at most one node creation (O(1)) and one pointer traversal (O(1)). Space: O(m) new nodes in the worst case (no shared prefix with existing words).

Duplicate inserts are handled naturally: if the word already exists, we simply walk the existing path and set isEnd = true (which is already true). No special case handling needed.

Search: start at the root. For each character in the word: if the current node has no child for this character, return false (the word does not exist). Move to the child. After all characters, return isEnd of the final node.

StartsWith: identical to search except the final check. Instead of returning isEnd, return true if we successfully traversed all prefix characters. We do not care whether the final node is a word end — any path matching the prefix suffices.

Both operations share the same traversal logic. A helper method traverse(word) that returns the final node (or null if the path breaks) can be used by both: search checks node.isEnd, startsWith checks node != null.

Insert "apple": root → create a → create p → create p → create l → create e (isEnd=true). Insert "app": root → a exists → p exists → p exists (set isEnd=true). Now "p" at depth 3 has isEnd=true.

Search "apple": root → a → p → p → l → e. isEnd=true → return true. Search "app": root → a → p → p. isEnd=true → return true. Search "ap": root → a → p. isEnd=false → return false.

StartsWith "app": root → a → p → p. Node exists → return true. StartsWith "apl": root → a → p → no child "l" at this "p" (the "l" is a child of the deeper "p"). Return false. The trie structure ensures precise prefix matching.

Python: class TrieNode: def __init__(self): self.children = {}; self.isEnd = False. class Trie: def __init__(self): self.root = TrieNode(). insert/search/startsWith use for loops over characters with self.root as starting point.

Java: class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isEnd = false; }. class Trie { TrieNode root = new TrieNode(); }. Use c - 'a' as the array index. Check children[index] != null for existence.

The Python dict-based approach and Java array-based approach are both clean. Python is about 20 lines total. Java is about 30 lines. Both are well within interview time constraints.

Time: O(m) for insert, search, and startsWith, where m is the length of the word or prefix. Each operation processes exactly m characters with O(1) work per character.

Space: O(n * m * 26) in the worst case for the array-based approach, where n is the number of words and m is the average word length. Each node allocates a 26-element array. The map-based approach uses O(n * m) — only allocated children consume space.

In practice, tries share prefixes extensively. If many words share common prefixes (like "apple", "application", "apply"), the actual space is much less than n * m. The prefix sharing is the trie's primary advantage over a hash set.

Design Add and Search Words (LeetCode 211) extends the trie with wildcard search: "." matches any character. The search method becomes a DFS that branches at wildcard positions. Direct extension of Implement Trie.

Word Search II (LeetCode 212) uses a trie to efficiently search for multiple words on a board simultaneously. The trie prunes DFS branches early when no word starts with the current path. A classic hard problem that combines tries with backtracking.

Replace Words (LeetCode 648) and Longest Word in Dictionary (LeetCode 720) are other trie applications. Together with Implement Trie, they cover the full spectrum of trie usage on LeetCode.