208. Implement Trie (Prefix Tree)

Most string problems hand you a data structure; this one asks you to be the data structure. Building a trie from scratch is the price of admission for autocomplete, spellcheck, and the harder word-search puzzles — and it’s the anchor of the trie pattern, so getting the three operations right here pays off across the whole cluster.

The problem

Design a Trie class that supports three operations: insert(word) adds a word, search(word) reports whether that exact word was inserted, and startsWith(prefix) reports whether any inserted word begins with that prefix. (Full statement on LeetCode.)

The distinction between the last two is the whole point. After inserting "apple", search("app") is false — "app" was never a full word — but startsWith("app") is true, because a stored word runs through it.

Intuition: one path per prefix, branch 26 ways

A hash set of words could answer search in $O(1)$, but it falls apart on startsWith — you’d have to scan every stored word to check for a shared prefix. The trie fixes that by making the characters the structure, not the words.

Picture a tree where each edge is a letter. To store "app" and "apple", you don’t keep two separate strings; you walk a → p → p once, and "apple" just extends that same path with l → e. Shared prefixes share nodes. That’s why a prefix query is cheap: walking the prefix is walking a single root-to-node path, and if the path exists at all, some word passes through it.

Each node holds up to 26 children (one slot per lowercase letter) and a single flag:

$\text{node} = (\text{children}[26],\; \text{isEnd})$

The isEnd flag is what separates a real word from a passed-through prefix. Landing on the last node of "app" tells you nothing on its own — you have to ask whether this node was marked as the end of an inserted word. That one boolean is the entire difference between search and startsWith.

Solution

All three methods share the same move: walk the string letter by letter, mapping each character to an index with c - 'a'. insert creates missing nodes as it goes; the two queries bail out the moment a link is missing.

class Trie {
    private final TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            // carve the path, creating nodes only where they don't exist yet
            if (node.children[i] == null) node.children[i] = new TrieNode();
            node = node.children[i];
        }
        node.isEnd = true;   // mark the final node as a complete word
    }

    public boolean search(String word) {
        TrieNode node = walk(word);
        // the path must exist AND end on a marked word
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        // any surviving path is enough; we don't care about isEnd here
        return walk(prefix) != null;
    }

    // follow the string; return the landing node, or null if a link breaks
    private TrieNode walk(String s) {
        TrieNode node = root;
        for (char c : s.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) return null;
            node = node.children[i];
        }
        return node;
    }

    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd = false;
    }
}

Pulling the shared traversal into walk keeps the two queries honest: search and startsWith differ by exactly one clause — whether the landing node’s isEnd matters. That’s the design mirroring the intuition.

Complexity

Let $L$ be the length of the word or prefix being processed.

Operation	Time	Space
insert	$O(L)$	$O(L)$ new nodes worst case
search / startsWith	$O(L)$	$O(1)$

Every operation touches at most $L$ nodes, independent of how many words are already stored — that constant-per-character cost is exactly what a hash-of-words approach can’t give you for prefixes.

In an interview

Draw the tree for two words that share a prefix ("app" and "apple") before writing a line — it makes the shared-node idea obvious and shows you’re designing, not reciting. Then state the node shape out loud: a 26-slot child array plus an isEnd flag.

The trap everyone hits is conflating search and startsWith. If you return true from search just because the path exists, you’ll pass on "apple" but wrongly accept "app" — you have to check isEnd. Naming why that flag exists is the tell that you understand the structure. If the interviewer hints the alphabet might be larger than 26 or include Unicode, swap the array for a HashMap<Character, TrieNode>; the logic is identical, you just trade $O(1)$ indexing for a little hashing overhead.

This node-walking skeleton is the foundation for the rest of the trie pattern. Next comes Add and Search Word, which threads . wildcards through this same tree with a small DFS, and Word Search II, which builds a trie of the dictionary and then hunts it across a board.

References

• LeetCode 208 — Implement Trie (Prefix Tree)