Implement Trie (Prefix Tree)

Problem in plain words

Build a Trie class with three operations on lowercase words: insert(word) stores a word, search(word) reports whether that exact word was stored, and startsWith(prefix) reports whether any stored word begins with the given prefix.

For example, after inserting "tree", search("tre") is false (no such full word) but startsWith("tre") is true.

Intuition

Store words as paths in a tree where every edge is a letter. Words with the same beginning share the same path for that beginning, so a prefix lookup is just walking down the letters. One extra boolean per node marks where a complete word ends, which is what separates search from startsWith. The trie insert and search lesson animates exactly this walk.

Approach

1. Each node holds children, an array of 26 references (one per letter), and isEnd, a boolean.
2. insert: start at the root. For each letter, create the child if it is missing and step into it. At the end, set isEnd = true.
3. Shared walk: write a helper that follows the letters of a string from the root and returns the last node reached, or null if some letter is missing.
4. search: the helper must return a node and that node's isEnd must be true.
5. startsWith: the helper must return a node; the flag does not matter.

Dry run

1. insert("car") creates root to c to a to r and marks r as an end.
2. insert("cat") reuses c and a, then creates a new child t under a and marks it as an end.
3. search("ca") reaches node a, but its isEnd is false: returns false.
4. startsWith("ca") reaches node a: returns true.
5. search("cat") reaches t with isEnd true: returns true. search("cab") finds no b under a: returns false.

Java solution

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

    private final Node root;

    public Trie() {
        root = new Node();
    }

    public void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new Node();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }

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

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

    private Node walk(String s) {
        Node node = root;
        for (int i = 0; i < s.length() && node != null; i++) {
            node = node.children[s.charAt(i) - 'a'];
        }
        return node;
    }
}

Python solution

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_end

    def startsWith(self, prefix: str) -> bool:
        return self._walk(prefix) is not None

    def _walk(self, s: str):
        node = self.root
        for ch in s:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

Complexity

Edge cases and common mistakes

• Prefix versus word: forgetting the isEnd check makes search("ca") return true after inserting "cat".
• Inserting the same word twice: the second insert just walks the existing path and sets the flag again, which is harmless.
• A word that is a prefix of another: inserting "cat" after "cats" only sets the flag on the existing t node; no new nodes are needed.
• Null checks while walking: stop as soon as a child is missing, or you will dereference null.