Implement Trie

Problem

LeetCode 208 — Implement Trie (Prefix Tree)

Implement a trie with insert(word), search(word), and startsWith(prefix).

Example

insert("apple")
search("apple")    →  true
search("app")      →  false
startsWith("app")  →  true
insert("app")
search("app")      →  true

Approach

Each node holds an array of 26 children (one per lowercase letter) and an isEnd flag. Every operation walks at most len(word) edges.

Key insight: search and startsWith differ by exactly one thing — whether the node at the end of the path must have isEnd == true. Extract a traverse helper that walks to the terminal node and reuse it for both.

Why array over HashMap

• Node[26] gives O(1) child lookup with no hashing or boxing overhead.
• Fixed size is fine — problem constraints guarantee lowercase English letters only.

Why iterative over recursive

Recursion with substring() creates a new String object at every level → O(L²) time and space per operation. Iterating over toCharArray() is O(L) with zero allocations.

Complexity

• Time: O(L) per operation where L is the length of the word/prefix
• Space: O(sum of all inserted characters) — bounded by total characters across all inserted words

Solution

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

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

    public boolean search(String word) {
        Node cur = traverse(word);
        return cur != null && cur.isEnd;
    }

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

    private Node traverse(String s) {
        Node cur = root;
        for (char c : s.toCharArray()) {
            cur = cur.children[c - 'a'];
            if (cur == null) return null;
        }
        return cur;
    }

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

Why It Teaches You Something

Once you know tries, a whole family of problems becomes trivial extensions: