Implement Trie (Prefix Tree)

mediumTrie & Strings101 stepsJava · Python · C++

A trie stores strings character by character along a tree, so words with a common prefix share nodes. insert walks down creating missing children and marks the last node as a word end; search walks down and checks that mark; startsWith only needs the walk to succeed.

▶ Watch the animated trace

Traced input: insert(apple), search(apple), search(app), startsWith(app), insert(app), search(app) → [null, null, true, false, true, null, true]. Original problem: neetcode.io/problems/implement-prefix-tree

Complexity

BestO(L)

AverageO(L)

WorstO(L)

SpaceO(total chars)

Each operation is linear in the word length L.

Key idea

Each node has up to 26 children, one per letter.
isEnd distinguishes a full word from a prefix ("app" vs "apple").
search and startsWith share the same walk; they differ only in the final check.

Common mistakes

Forgetting isEnd: then search("app") would be true after inserting only "apple".
Using a HashMap per node is fine for large alphabets but slower for a–z.

Solution

Java

class Trie {
    class Node {
        Node[] next = new Node[26];
        boolean isEnd;
    }

    private final Node root = new Node();

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

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

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

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

Python

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


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

    def insert(self, word: str) -> None:
        cur = self.root
        for c in word:
            cur = cur.next.setdefault(c, TrieNode())
        cur.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) -> Optional[TrieNode]:
        cur = self.root
        for c in s:
            cur = cur.next.get(c)
            if cur is None: return None
        return cur

C++

class Trie {
    struct Node {
        Node* next[26] = {};
        bool isEnd = false;
    };

    Node* root = new Node();

    Node* walk(const string& s) {
        Node* cur = root;
        for (char c : s) {
            cur = cur->next[c - 'a'];
            if (!cur) return nullptr;
        }
        return cur;
    }

public:
    void insert(string word) {
        Node* cur = root;
        for (char c : word) {
            if (!cur->next[c - 'a']) cur->next[c - 'a'] = new Node();
            cur = cur->next[c - 'a'];
        }
        cur->isEnd = true;
    }

    bool search(string word) {
        Node* node = walk(word);
        return node && node->isEnd;
    }

    bool startsWith(string prefix) {
        return walk(prefix) != nullptr;
    }
};

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Search on an empty trie The root has no children.	`search(a)`	`[null, false]`
Prefix is not a word The 'a' node exists but isn't marked as a word end.	`insert(car), search(ca), startsWith(ca)`	`[null, null, false, true]`
Word longer than any stored The walk falls off the trie after "go".	`insert(go), search(gone)`	`[null, null, false]`