Implement Trie (Prefix Tree) — Practice

Problem

Implement a Trie with insert(word), search(word) (exact match), and startsWith(prefix) (prefix match) operations.

Examples

Example 1

Input: insert("apple"); search("apple") -> true; search("app") -> false; startsWith("app") -> true

Output: as shown

Explanation: "app" was never inserted as a complete word, so search returns false, but it IS a valid prefix of "apple", so startsWith returns true.

Constraints

•1 <= word/prefix length <= 2000
•Lowercase English letters only

Hints

Hint 1

Each Trie node needs: a fixed-size array (or map) of child nodes, one per possible next character, and a boolean marking 'a complete word ends here.'

Hint 2

insert() walks the tree character by character, creating a new child node whenever the needed path doesn't exist yet.

Hint 3

search() and startsWith() share almost all their logic — the only difference is whether the final node needs isEndOfWord=true (search) or just needs to exist at all (startsWith).

Solutions

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

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

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) node.children[index] = new TrieNode();
            node = node.children[index];
        }
        node.isEndOfWord = true; // mark the END of this specific word, not every node along the path
    }

    public boolean search(String word) {
        TrieNode node = findNode(word);
        return node != null && node.isEndOfWord; // must be a complete inserted word, not just any valid path
    }

    public boolean startsWith(String prefix) {
        return findNode(prefix) != null; // just needs the path to exist — no isEndOfWord requirement
    }

    private TrieNode findNode(String s) {
        TrieNode node = root;
        for (char c : s.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) return null; // path doesn't exist
            node = node.children[index];
        }
        return node;
    }
}

Time: O(L) per operation, L = word/prefix length · Space: O(N * L) total across all inserted words, N = word count