164. Implement Trie (Prefix Tree)

Store the words as overlapping paths in a tree, one edge per character. Every node is a map from a character to a child node, and a node flagged as a word-end marks that the path taken to reach it spells a complete inserted word. Because shared prefixes share the same nodes, search and startsWith are just walks down the tree that cost only as much as the query's length — independent of how many words are stored.

The data structure

A trie is a tree where each edge is labeled with one character and each path from the root spells a prefix. We represent every node as a dictionary (hash map) from a character to its child node. One extra key — here "$" — marks a node as the end of an inserted word. (In an array-backed version, the map is a fixed 26-slot array and a boolean isEnd flag replaces "$".)

The power of the trie is that words sharing a prefix share the same nodes. Inserting apple and then app reuses the a → p → p path; the difference is only which nodes carry the end-of-word mark.

insert(word)

Walk from the root, one character at a time. For each character, follow the existing child if present, otherwise create a new empty node and follow it. After consuming the whole word, mark the final node as a word-end.

The key distinction: search vs. startsWith

Both walk the same way — follow the child for each character; if a child is ever missing, the answer is immediately false. They differ only at the end of the walk:

• search(word) must land on a node and that node must carry the end-of-word mark. Reaching the node isn't enough — app is a valid path after inserting apple, but it was never marked as a word.
• startsWith(prefix) only needs to reach the node. Any node existing means some inserted word passes through this prefix.

Algorithm

• insert(word): node = root; for each c in word, node = node.children[c] (create if absent); mark node as end.
• find(word): node = root; for each c, if c not in node.children return null, else descend; return node.
• search(word): n = find(word); return n != null && n.isEnd.
• startsWith(prefix): return find(prefix) != null.

Worked example

Start empty, then run: insert("apple"), search("apple"), search("app"), startsWith("app"), insert("app"), search("app").

Complexity

• Time: O(L) per operation, where L is the length of the word or prefix — independent of the number of stored words.
• Space: O(total characters inserted) in the worst case (no shared prefixes).

class Trie {
    private Trie[] children = new Trie[26];
    private boolean isEnd = false;

    public Trie() {}

    public void insert(String word) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) node.children[i] = new Trie();
            node = node.children[i];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        Trie node = find(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return find(prefix) != null;
    }

    private Trie find(String word) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) return null;
            node = node.children[i];
        }
        return node;
    }
}