Implement Trie (Prefix Tree)

MediumTrie (Prefix Tree)Blind 75MidOpen on LeetCodeUpdated Sep 21, 2026

Design a class that stores lowercase words and supports three operations. insert(word) adds word and returns nothing. search(word) returns true only if that exact word has been inserted. startsWith(prefix) returns true if any inserted word begins with prefix, and a whole word counts as a prefix of itself. Each example is a sequence of calls on one fresh object, and its output lists what each search and startsWith call returns, in order.

Examples

insert("apple"); search("apple") returns true

After "apple" is inserted, searching for that exact word finds it, so search returns true.

insert("apple"); search("app"); startsWith("app") returns false, true

The letters of "app" lead into "apple", but no stored word ends after the second p.

"app" was never inserted as a word, so search("app") is false. It is the start of "apple", so startsWith("app") is true.

insert("apple"); search("app"); insert("app"); search("app") returns false, true

The first search("app") is false because only "apple" is stored. Once "app" is inserted, the same search returns true.

Constraints

1 <= word.length, prefix.length <= 2000
Lowercase English letters.

Hints

Hint 1

Words that share prefixes can share storage, what structure mirrors that sharing?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Store words in a tree of nodes with one edge per character; each node holds a map of child letters and an end flag. insert walks down from the root, creating missing children, and sets end on the last node. search and startsWith share a helper that follows the characters and returns the node reached, or None. search also needs that node's end flag; startsWith only needs the node to exist. O(L) per call, L = string length; O(T) space, T = total characters inserted.

Time

O(L) per call

Space

O(T)

Pitfall

Letting search return true whenever the path exists: after inserting only "apple", search("app") must be false. The end flag set by insert is the only thing that tells a stored word apart from a prefix.

Solutions

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

    private final Node root = new Node();

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

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

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

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

class Trie:
    def __init__(self):
        self.children = {}
        self.end = False

    def insert(self, word: str) -> None:
        node = self
        for c in word:
            if c not in node.children:
                node.children[c] = Trie()
            node = node.children[c]
        node.end = True

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

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

    def _find(self, s: str):
        node = self
        for c in s:
            if c not in node.children:
                return None
            node = node.children[c]
        return node