Implement Trie (Prefix Tree) — Insert, Search, StartsWith

Problem Statement#

LeetCode 208 — Implement Trie (Prefix Tree) | Difficulty: Medium

Design and implement a Trie (prefix tree) with the following operations:

• insert(word) — Insert a word into the trie.
• search(word) — Return true if the word is in the trie.
• startsWith(prefix) — Return true if any word in the trie starts with the given prefix.

Constraints:

• 1 <= word.length, prefix.length <= 2000
• word and prefix consist of lowercase English letters only.
• At most 3 * 10^4 calls in total to insert, search, and startsWith.

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.insert("apple")   → stores "apple"
trie.search("apple")   → true  (exact match)
trie.search("app")     → false ("app" not inserted)
trie.startsWith("app") → true  ("apple" starts with "app")
trie.insert("app")     → stores "app"
trie.search("app")     → true  (now inserted)

Input: insert("cat"), search("cat"), search("ca"), startsWith("ca")
Output: null, true, false, true

Input: insert("hello"), insert("help"), startsWith("hel"), search("helo")
Output: null, null, true, false

Why This Problem Matters#

The Trie is the gateway to an entire category of prefix-based interview problems. Every company that deals with search — Google, Amazon, Uber — uses trie-like structures in production. Autocomplete, spell checking, IP routing, and contact search are all backed by tries.

More importantly, LC 208 is the template you modify for every harder trie problem. Get this one perfectly memorized and the rest become straightforward variations.

The Core Insight#

A trie is a tree where each node represents a single character and the path from root to a node spells out a prefix. Three key design decisions:

1. Node structure — each node holds a dictionary/array of child pointers and a boolean is_end flag marking where complete words terminate.
2. Insert — walk character by character, create nodes on demand, set is_end = True at the last character.
3. Search vs startsWith — search requires reaching the end node AND is_end = True; startsWith only needs to reach the end of the prefix (no is_end check).

Trie after inserting "app" and "apple":
 
root
 └── 'a'
      └── 'p'
           └── 'p' [is_end=True]   ← "app"
                └── 'l'
                     └── 'e' [is_end=True]  ← "apple"

The is_end flag is the critical detail beginners miss — without it, search("app") would incorrectly return true even if only "apple" was inserted.

Visual Dry Run#

Let us trace: insert("cat"), insert("car"), search("cat"), startsWith("ca"), search("cap").

After insert("cat"):

root → 'c' → 'a' → 't'[end]

After insert("car"):

root → 'c' → 'a' → 't'[end]
                 → 'r'[end]

search("cat"):

• root has 'c'? Yes → move to 'c' node
• 'c' node has 'a'? Yes → move to 'a' node
• 'a' node has 't'? Yes → move to 't' node
• Is 't' node is_end? Yes → return True

startsWith("ca"):

• root → 'c' → 'a' → reached end of prefix
• Return True (no is_end check needed)

search("cap"):

• root → 'c' → 'a' → look for 'p' in 'a' node
• 'a' only has 't' and 'r' children → return False

Common Mistakes#

1. Forgetting is_end in search — If you only check whether the path exists, search("app") returns true even when only "apple" was inserted. Always check is_end at the final node.

2. Checking is_end in startsWith — The opposite mistake: startsWith should NOT require is_end. Any valid path to the prefix end returns true.

3. Returning node instead of node.is_end — Beginners often write return node at the end of search, which returns the node object (truthy) instead of the boolean flag.

4. Not initializing children properly — Using a plain dict means you must check if c not in node.children before accessing. Forgetting this check causes KeyError.

5. Reusing node as root — A common Java/Python mistake is making the Trie class itself the node (its own children array). This works but blurs the distinction between the trie container and individual nodes. A separate TrieNode class is cleaner.

6. Handling empty string — insert("") or search("") with an empty string should short-circuit gracefully. Most problems guarantee non-empty input, but check constraints.

7. Array vs HashMap children — An array of 26 children wastes memory if the alphabet is large (Unicode). A HashMap is more flexible but slightly slower. For lowercase English, a 26-array is fine.

Solutions#

Python — HashMap Children#

class TrieNode:
    def __init__(self):
        # Dictionary maps character → child TrieNode
        self.children = {}
        # True only when this node is the END of a complete word
        self.is_end = False
 
class Trie:
    def __init__(self):
        # Root node holds no character itself; it's the entry point
        self.root = TrieNode()
 
    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            # Create child node if this character path doesn't exist yet
            if ch not in node.children:
                node.children[ch] = TrieNode()
            # Move deeper into the trie along this character
            node = node.children[ch]
        # Mark end-of-word AFTER processing all characters
        node.is_end = True
 
    def search(self, word: str) -> bool:
        node = self.root
        for ch in word:
            # If any character is missing, word is not in trie
            if ch not in node.children:
                return False
            node = node.children[ch]
        # Must also confirm this is a complete word, not just a prefix
        return node.is_end
 
    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for ch in prefix:
            # If any character in prefix is missing, no word has this prefix
            if ch not in node.children:
                return False
            node = node.children[ch]
        # Reaching here means prefix path exists — no is_end check needed
        return True

JavaScript — Array Children (26 slots)#

class TrieNode {
    constructor() {
        // Fixed-size array: index 0='a', 1='b', ..., 25='z'
        // null means no child for that character
        this.children = new Array(26).fill(null);
        // Marks whether a complete word ends at this node
        this.isEnd = false;
    }
}
 
class Trie {
    constructor() {
        // Root node: no character, just the entry point
        this.root = new TrieNode();
    }
 
    insert(word) {
        let node = this.root;
        for (const ch of word) {
            // Convert character to 0-based index: 'a'→0, 'b'→1, ...
            const idx = ch.charCodeAt(0) - 97;
            // Allocate a new node if this slot is empty
            if (!node.children[idx]) {
                node.children[idx] = new TrieNode();
            }
            // Descend to child node
            node = node.children[idx];
        }
        // All characters consumed — mark end of word
        node.isEnd = true;
    }
 
    search(word) {
        let node = this.root;
        for (const ch of word) {
            const idx = ch.charCodeAt(0) - 97;
            // Missing child means word doesn't exist
            if (!node.children[idx]) return false;
            node = node.children[idx];
        }
        // Path exists — but is it a complete word?
        return node.isEnd;
    }
 
    startsWith(prefix) {
        let node = this.root;
        for (const ch of prefix) {
            const idx = ch.charCodeAt(0) - 97;
            // If any prefix character is missing, no match
            if (!node.children[idx]) return false;
            node = node.children[idx];
        }
        // Prefix path fully traversed — at least one word has this prefix
        return true;
    }
}

Complexity Analysis#

Where L = average word length, N = number of words.

• Array children: O(26 * nodes) space — predictable, cache-friendly.
• HashMap children: O(actual children * nodes) space — better for sparse alphabets.

Follow-up Questions#

• How would you delete a word from the trie? — Recurse to the end node, clear is_end, then unlink nodes bottom-up if they have no other children and no other is_end.
• How would you support case-insensitive search? — Normalize to lowercase on insert and query, or expand children array to 52.
• How would you count words with a given prefix? — Add a count field to each node, increment on insert, return count at prefix end (see LC 2185).
• Can you serialize/deserialize a trie? — Yes: BFS level-order or DFS pre-order with child counts.

This Pattern Solves#

• Any "prefix matching" problem (autocomplete, suggest products).
• "Does word exist?" in a set of words — O(L) vs O(L) for hashset, but trie also handles prefix queries.
• Problems where you need to simultaneously search multiple words (word search grid, stream matching).
• Binary trie: XOR maximization problems where you insert bit-by-bit.

Key Takeaways#

• A trie node consists of two fields: children (a map or fixed-size array) and an is_end boolean flag — that is the entire structure.
• insert walks existing nodes and creates missing ones; search walks and checks is_end at the final character; startsWith walks without the is_end check.
• Use a fixed-size children[26] array (or equivalent) for ASCII-only inputs — faster constant than a hash map; use a hash map for Unicode or when the character set is unknown.
• All three operations run in O(L) time where L is the word length — independent of the number of words stored.
• A trie with n words of average length L uses O(n * L) space in the worst case (no shared prefixes) and much less when prefixes are shared.
• The binary trie variant (insert bit-by-bit from MSB) enables O(log(max_val)) XOR maximization queries for problems like LC 421.
• This insert/search/startsWith template is the foundation for autocomplete, word search grids, stream matching, and every trie problem variant.