Implement Trie LeetCode 208 — Prefix Tree

LeetCode 208 — Implement Trie (Prefix Tree) — asks you to design a Trie class that supports three operations: insert(word) adds a word to the data structure, search(word) returns true if the exact word is in the trie, and startsWith(prefix) returns true if any previously inserted word starts with that prefix. All inputs consist of lowercase English letters only.

The Trie is one of the most important data structures in computer science for string-heavy applications. It powers autocomplete in search engines, spell checkers, IP routing tables, and word games. Mastering LeetCode 208 unlocks a family of related problems: Word Search II (212) uses a Trie to prune DFS on a board, Add and Search Words (211) extends the Trie with wildcard matching, and Design Search Autocomplete System (642) builds a full autocomplete feature on top of a Trie.

The key insight is that a Trie beats a hash set for prefix queries. A hash set supports O(1) exact-word lookup but cannot answer prefix queries without scanning all stored words. A Trie answers both exact-word and prefix queries in O(m) time — the same time it takes to simply read the query string — making it asymptotically optimal for this class of problem.

A Trie (pronounced "try", from re-TRIE-val) is a tree where each node represents one character, and paths from the root to a node spell out prefixes. The root node itself holds no character — it is the empty string. From the root, each child edge represents the first character of a word. From any node at depth d, each child edge extends the prefix by one more character to depth d+1.

Nodes marked as "end of word" (isEnd = true) indicate that the path from the root to that node spells a complete word that was inserted. A node can be both an interior node and an end-of-word node simultaneously — for example, if both "app" and "apple" are inserted, the node at depth 3 for the third character of both words has isEnd = true (for "app") and also has a child leading to the "l" of "apple".

Shared prefixes share nodes. If "apple", "apply", "apt", and "ape" are all inserted, the first node from the root for "a" is shared by all four words. The "ap" prefix shares two nodes. This structural sharing is why Tries are space-efficient for large vocabularies with common prefixes — such as English words, URLs with the same domain, or method names in a codebase.

Each TrieNode has two fields: children and isEnd. The children field maps characters to child TrieNodes — implemented as a Python dict or a Java HashMap<Character, TrieNode> for flexibility, or as a fixed-size array of 26 entries (one per lowercase letter) for maximum speed. The isEnd boolean is false by default and set to true when a word terminates at this node.

The Trie class itself contains only a single field: root, a TrieNode initialized with empty children and isEnd = false. All three operations — insert, search, startsWith — begin at root and traverse downward. No other instance state is needed; the entire trie structure is encoded in the root node and its descendants.

Choosing between a dict and an array of 26 for children is a space-vs-speed trade-off. A dict is more memory-efficient when each node has few children (sparse trie) — it only allocates entries that exist. An array of 26 is slightly faster for lookups (direct index by character offset) and is simpler to implement, but allocates 26 pointers per node even if most are null (dense allocation).

Insert walks from the root one character at a time. For each character in the word, check whether a child node for that character already exists. If it does, move to that child. If it does not, create a new TrieNode, add it to the current node's children dict under that character, then move to the new node. After processing all characters in the word, mark the current node's isEnd = true.

Insert never overwrites existing nodes — it only creates new ones where gaps exist. Inserting "apple" after "app" is already in the trie creates two new nodes (for "l" and "e") but reuses the existing nodes for "a", "p", and "p". This is what makes shared-prefix storage efficient: each new word only pays for the characters not already in the trie.

The time complexity of insert is O(m) where m is the length of the word — it processes exactly one character per step and performs O(1) work at each step (dict lookup and optional node creation). The space complexity is O(m) in the worst case (if the word shares no prefix with any existing word, m new nodes are created) and O(1) in the best case (if the word is already fully represented in the trie).

Search and startsWith share the same traversal logic but differ in one critical detail: what they check at the end. Both start at root and walk the trie character by character. If at any point the required child node does not exist, the word or prefix is not in the trie — both return false immediately. If the traversal completes (all characters processed), the functions diverge.

For search(word), once traversal of all characters completes, check whether the final node has isEnd = true. If yes, the exact word was inserted and return true. If no, the word exists only as a prefix of a longer word — for example, "app" might exist as a prefix of "apple" but if "app" itself was never inserted, search("app") must return false. The isEnd flag is the key distinguishing feature.

For startsWith(prefix), once traversal of all characters completes, simply return true. There is no need to check isEnd because startsWith only asks whether any inserted word begins with this prefix — and the fact that we successfully traversed all prefix characters proves that at least one such word was inserted. StartsWith is therefore slightly simpler than search.

Python implementation uses a TrieNode class with children = {} and isEnd = False. The Trie class holds self.root = TrieNode(). Insert: node = self.root; for char in word: if char not in node.children: node.children[char] = TrieNode(); node = node.children[char]; node.isEnd = True. Search: traverse like insert but without creation; return node.isEnd at end. StartsWith: same traversal; return True at end. All three are O(m) time and O(m) space for insert, O(m) time O(1) space for search and startsWith.

Java implementation defines a TrieNode class with TrieNode[] children = new TrieNode[26] and boolean isEnd = false. The Trie class initializes root = new TrieNode(). Insert: TrieNode node = root; for (char c : word.toCharArray()) { int idx = c - 'a'; if (node.children[idx] == null) node.children[idx] = new TrieNode(); node = node.children[idx]; } node.isEnd = true. Search and startsWith follow the same traversal pattern with the same terminal condition difference. Using an array of 26 avoids boxing/unboxing overhead and gives cache-friendly access.

Space complexity for the full trie is O(total characters across all inserted words) in the worst case (no shared prefixes) and much less when words share common prefixes. With up to 3 * 10^4 operations and words up to 2000 characters, the trie can hold at most 6 * 10^7 characters worth of nodes — but in practice, shared English-word prefixes keep actual node counts far lower.

Word Search II (LeetCode 212) combines a Trie with DFS backtracking on a 2D board. Instead of checking each word individually against the board (O(words * 4^L)), build a Trie of all target words, then DFS from every cell, pruning entire branches when the current path is no longer a prefix of any target word. The Trie reduces the search space dramatically — this is the classic application that makes Tries shine in practice.

Add and Search Words Data Structure (LeetCode 211) extends the basic Trie with wildcard matching: the '.' character in a search pattern can match any single letter. This requires a recursive DFS over children at each wildcard position. The base Trie structure from LeetCode 208 handles all non-wildcard characters; you add a recursive search that iterates all children when a '.' is encountered.

Other Trie family problems include Design Search Autocomplete System (642), Replace Words (648), Maximum XOR of Two Numbers in an Array (421 — uses a binary Trie), and Palindrome Pairs (336). All of these build on the core TrieNode + traversal pattern from LeetCode 208. Mastering insert, search, and startsWith here gives you the foundation for every advanced Trie variant.