What is the brute force approach and complexity for Implement Trie (Prefix Tree)?

Store words in a vector; search and startsWith check every stored word with time complexity O(N · L) and space complexity O(T).

What is the optimal approach and complexity for Implement Trie (Prefix Tree)?

One node per letter, children by letter, and a flag where a word ends with optimal time complexity O(L) and space complexity O(26 · T).

How do you identify the pattern for Implement Trie (Prefix Tree)?

Look for key signals in the prompt: "many words" indicates Words share their first letters, so store each letter once as a node and let words share the top of the tree.; "prefix" indicates A prefix is just a path from the root, so checking it is a walk down the tree with no scanning.; "exact word vs prefix" indicates Two questions on the same path. The path answers the prefix question, and one flag per node answers the word question..

Implement Trie (Prefix Tree)

Medium·LeetCode #208Basic Anchor

LeetCode

Jump:

30-Second Mental ModelTrie (prefix tree) with an end-of-word flag

Complexity:O(N · L)→O(L)

Key Insight

Each node has 26 child slots, one per letter, and an isEnd flag. Insert walks down from the root, creating missing nodes, and sets isEnd on the last node. Search and startsWith walk the same path but never create anything. The path answers the prefix question, and only the isEnd flag answers the exact-word question.

Core Validity Invariant

A node exists for a prefix exactly when some stored word starts with that prefix, and isEnd is true exactly when that prefix is itself a stored word.

Problem

Build a Trie class. It stores words and answers two questions about them:

search(word) is true only if this exact word was stored.
startsWith(prefix) is true if at least one stored word begins with prefix.

A shorter piece of a stored word is a prefix, not a word. After apple is stored, search("app") is false, but startsWith("app") is true.

Trie() makes an empty trie, and insert(word) stores a word.

Input

The calls in order: Trie() first, then any mix of insert, search and startsWith. Every word and prefix uses only lowercase letters a to z.

Output

For each search and startsWith, true or false. Trie() and insert return nothing (shown as null below).

Example 1

Input: Trie(), insert("apple"), search("apple"), search("app"), startsWith("app"), insert("app"), search("app")

Output: null, null, true, false, true, null, true

After apple is stored, apple is found, but app is not: it is only a prefix. startsWith("app") is true because apple starts with app. Once app is inserted as a word, search("app") is true.

Example 2

Input: Trie(), insert("cat"), startsWith("ca"), search("ca"), search("dog")

Output: null, null, true, false, false

cat starts with ca, so startsWith("ca") is true. But ca was never stored as a word, and dog was never stored at all.

Constraints

• 1 ≤ word.length, prefix.length ≤ 2000
• word and prefix use only lowercase letters a to z
• At most 3 · 10^4 calls in total to insert, search and startsWith

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If I store apple as one whole string, how would I check app? Could I reuse anything I did for apple?
2.
Words that start with the same letters, like app and apple, could share their first letters. What would that look like as a tree?
3.
What does one node need to hold? Think about the letters that can come next, and whether a word stops right there.
4.
search("app") and startsWith("app") walk the same letters. What is the one difference in their answers?
5.
When a letter has no node during a search, what can I say about the answer? What changes during an insert?

Brute force approach

Idea

Keep every inserted word in a vector<string>. search compares the whole query with each stored word. startsWith compares the first letters of each stored word with the prefix. Both can take a full pass over the list.

Thinking process

1
The simplest store is a list, so insert just adds the word at the end.
2
For search, the word is stored only if one entry equals it exactly. So I compare with each entry until one matches.
3
For startsWith, I need one stored word whose first letters equal the prefix. So I compare only the first letters of each entry.
4
Example: after insert apple and insert app, the list is [apple, app]. search(app) checks apple (not equal), then app (equal), so it is true. startsWith(ap) stops at apple, because its first two letters are ap.

Code & Implementation

brute.cpp

class Trie {
    // Every inserted word, in the order it came in. No structure at all.
    vector<string> words;

public:
    Trie() {}

    void insert(string word) {
        words.push_back(word);
    }

    bool search(string word) {
        // Exact match: the whole word must equal a stored word.
        for (const string& w : words) {
            if (w == word) return true;
        }
        return false;
    }

    bool startsWith(string prefix) {
        // The first letters of a stored word must equal the prefix.
        for (const string& w : words) {
            if (w.size() >= prefix.size() && w.compare(0, prefix.size(), prefix) == 0) return true;
        }
        return false;
    }
};

import java.util.ArrayList;
import java.util.List;

class Trie {
    private List<String> words;

    public Trie() {
        words = new ArrayList<>();
    }

    public void insert(String word) {
        words.add(word);
    }

    public boolean search(String word) {
        for (String w : words) {
            if (w.equals(word)) return true;
        }
        return false;
    }

    public boolean startsWith(String prefix) {
        for (String w : words) {
            if (w.startsWith(prefix)) return true;
        }
        return false;
    }
}

class Trie:
    def __init__(self):
        self.words: list[str] = []

    def insert(self, word: str) -> None:
        self.words.append(word)

    def search(self, word: str) -> bool:
        return word in self.words

    def startsWith(self, prefix: str) -> bool:
        return any(w.startswith(prefix) for w in self.words)

export class Trie {
    private words: string[];

    constructor() {
        this.words = [];
    }

    insert(word: string): void {
        this.words.push(word);
    }

    search(word: string): boolean {
        return this.words.includes(word);
    }

    startsWith(prefix: string): boolean {
        return this.words.some(w => w.startsWith(prefix));
    }
}

Complexity

Time O(N · L)Space O(T)

Insert is cheap, but every search and startsWith can scan the whole list. If about half of the 3 · 10^4 calls insert words, one query can compare about 1.5 · 10^4 stored words, and each comparison can take up to 2000 letter steps. That is far too slow. search and startsWith compare with up to N stored words; L is the length of the word or prefix. T is the total number of letters stored.

Optimized approach

Idea

Start from brute force

The list keeps whole words, so every search and startsWith has to look through all of them one by one.

Find the repeated work

Words that start the same way, like apple, app and apply, are compared letter by letter again and again. Nothing is shared between the stored words.

Define the state — what variables do I need?

root: The empty prefix. Every word starts here.
node.children[c]: The node for the next letter c (a to z), or nullptr if no stored word continues that way.
node.isEnd: True if a stored word ends at this node. A path can exist while this is false.

Define validity

A node exists for a prefix exactly when some stored word starts with that prefix, and isEnd is true exactly when that prefix is itself a stored word.

Define the transitions — when does each pointer move, and why is it safe?

insert(word), a letter has no child

create the child node for that letter

The path needs this letter before we can go deeper, so the node has to exist.

insert(word), after the last letter

set isEnd = true on the current node

The word now ends here. Words that pass through this node are not changed.

search or startsWith, a letter has no child

stop and return false

No stored word has these letters as a start, so none can start with the prefix or equal the word.

search, the walk finishes

return the node's isEnd

The path exists, but it only counts as a word if a stored word ends at this node.

startsWith, the walk finishes

return true

Every node on the path was created by some insert, so some stored word has this prefix.

What does the current window add to the answer?

Each call does one walk of L letters. search reads the flag at the end of the walk; startsWith only needs the walk to finish.

Code & Implementation

optimal.cpp

class Trie {
    // One node per letter position. children[c] is the next letter 'a' + c.
    struct Node {
        Node* children[26] = {};
        bool isEnd = false;   // a stored word ends at this node
    };
    Node* root;

    // Follows the letters of s from the root. Returns the node reached,
    // or nullptr as soon as a letter has no child.
    Node* walk(const string& s) {
        Node* cur = root;
        for (char ch : s) {
            cur = cur->children[ch - 'a'];
            if (!cur) return nullptr;
        }
        return cur;
    }

    // Frees a node and everything below it.
    static void destroy(Node* n) {
        if (!n) return;
        for (Node* child : n->children) destroy(child);
        delete n;
    }

public:
    Trie() : root(new Node()) {}
    ~Trie() { destroy(root); }

    // The trie owns its nodes, so copies are not allowed.
    Trie(const Trie&) = delete;
    Trie& operator=(const Trie&) = delete;

    void insert(string word) {
        Node* cur = root;
        for (char ch : word) {
            // Create the node for this letter only when the slot is empty.
            Node*& child = cur->children[ch - 'a'];
            if (!child) child = new Node();
            cur = child;
        }
        cur->isEnd = true;   // the word ends here
    }

    bool search(string word) {
        Node* node = walk(word);
        return node != nullptr && node->isEnd;   // the path exists AND a word ends here
    }

    bool startsWith(string prefix) {
        return walk(prefix) != nullptr;          // the path exists is enough
    }
};

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

    private final Node root;

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

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

    public void insert(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (cur.children[idx] == null) {
                cur.children[idx] = new Node();
            }
            cur = cur.children[idx];
        }
        cur.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;
    }
}

class Node:
    def __init__(self):
        self.children: dict[str, Node] = {}
        self.is_end: bool = False

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

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

    def _walk(self, s: str) -> Node | None:
        cur = self.root
        for ch in s:
            if ch not in cur.children:
                return None
            cur = cur.children[ch]
        return cur

    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

class TrieNode {
    children: (TrieNode | null)[] = new Array(26).fill(null);
    isEnd: boolean = false;
}

export class Trie {
    private root: TrieNode;

    constructor() {
        this.root = new TrieNode();
    }

    private walk(s: string): TrieNode | null {
        let cur: TrieNode | null = this.root;
        for (let i = 0; i < s.length; i++) {
            const idx = s.charCodeAt(i) - 97;
            if (!cur.children[idx]) return null;
            cur = cur.children[idx];
        }
        return cur;
    }

    insert(word: string): void {
        let cur = this.root;
        for (let i = 0; i < word.length; i++) {
            const idx = word.charCodeAt(i) - 97;
            if (!cur.children[idx]) {
                cur.children[idx] = new TrieNode();
            }
            cur = cur.children[idx]!;
        }
        cur.isEnd = true;
    }

    search(word: string): boolean {
        const node = this.walk(word);
        return node !== null && node.isEnd;
    }

    startsWith(prefix: string): boolean {
        return this.walk(prefix) !== null;
    }
}

Complexity

Time O(L)Space O(26 · T)

Each call takes at most L steps, so 3 · 10^4 calls with words up to 2000 letters take at most about 6 · 10^7 steps. Words that share a start share nodes, so the trie never has more nodes than letters inserted. Every call walks one node per letter, so it costs O(L), where L is the length of the word or prefix. T is the total number of letters inserted; each one adds at most one node with 26 child pointers.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Store words in a vector; search and startsWith check every stored word	O(N · L)	O(T)
Optimal	One node per letter, children by letter, and a flag where a word ends	O(L)	O(26 · T)

Why does this belong to this pattern?

Clues in the problem statement

“many words”Words share their first letters, so store each letter once as a node and let words share the top of the tree.
“prefix”A prefix is just a path from the root, so checking it is a walk down the tree with no scanning.
“exact word vs prefix”Two questions on the same path. The path answers the prefix question, and one flag per node answers the word question.

one node per letter+a path from the root = a prefix+isEnd flag = a whole stored word→Trie (prefix tree) with an end-of-word flag

This is the anchor of the Trie pattern. A prefix question is a walk, and the walk either finishes or falls off. The path tells you about prefixes, and the isEnd flag tells you about whole words. Because apple and app share their first three nodes, each shared letter is stored and checked once. Later trie questions build on this: Replace Words stops at the first end flag it meets, and Search Suggestions keeps a short list at each node.

Don't make this mistake

Pattern confusion: search returns true for a prefix

✗ bool search(string word) { return walk(word) != nullptr; // forgot isEnd }

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

Insert apple, then call search with app. The walk reaches the second p, so the wrong version returns true. The right answer is false, because app was never inserted as a word. Only the isEnd flag says a word stops there.

startsWith checks isEnd instead of the walk

✗ bool startsWith(string prefix) { Node* node = walk(prefix); return node != nullptr && node->isEnd; }

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

Insert apple, then call startsWith with app. The path exists, so the answer is true. The wrong version checks isEnd, gets false, and says no stored word starts with app, which is wrong. A prefix does not need to be a word.

Following a missing child (crash)

✗ Node* cur = root; for (char ch : word) cur = cur->children[ch - 'a']; // cur may become nullptr return cur->isEnd;

✓ Node* cur = root; for (char ch : word) { cur = cur->children[ch - 'a']; if (!cur) return false; // no node for this letter: stop } return cur->isEnd;

Insert apple, then search apply. The walk goes a, p, p, l, then y has no node, so cur becomes nullptr. The last line reads cur->isEnd on nothing, and the program crashes. Stop as soon as a letter is missing.

Replacing a node that already exists

✗ for (char ch : word) { cur->children[ch - 'a'] = new Node(); // throws away the old node and its subtree cur = cur->children[ch - 'a']; }

✓ Node*& child = cur->children[ch - 'a']; if (!child) child = new Node(); // reuse the node if it is already there cur = child;

Insert apple, then insert app. The wrong version replaces the first a node, and with it the whole p, p, l, e branch. Then search apple returns false, even though it was inserted. Only create a node when its slot is empty.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Trie translate into production architectures and low-level memory mechanics.

LLD Practice

Autocomplete & Search Engine

Prefix query caching, ranking, and memory-efficient trie compaction.

Explore Track

C++ Internals

Memory Alignment & Struct Padding

Minimizing pointer overhead and cache misses across 26-ary trie nodes.

Explore Track

Replace Words