Skip to content

Volume ITechnology

4.15.1 — Implement Trie (Prefix Tree) ​

LeetCode 208 · Medium · ★ Blind 75

The problem ​

Build a data structure with three operations:

  • insert(word)
  • search(word) — is this exact word stored?
  • startsWith(prefix) — is any stored word starting with this prefix?

To make this concrete, imagine you are building an autocomplete system. You insert words like "apple", "app", and "apricot". If a user types "app", startsWith("app") should return true because there are words starting with that prefix, and search("app") should also return true because we explicitly inserted "app". However, search("ap") would return false because we never inserted "ap" as a standalone word, even though startsWith("ap") is true. We can assume all inputs consist entirely of lowercase English letters a-z, and words can be up to 2000 characters long.

The pattern ​

A hash set answers search in O(1), but it cannot answer startsWith at all without checking every stored word. Prefix questions need a structure organised by prefix, and that is a trie.

A trie is a tree where each edge is a character and each path from the root spells a prefix. Words sharing a prefix share the nodes for it.

Think of a trie like a massive physical file cabinet system. The first cabinet is labeled with the first letter of the word, the drawer inside is labeled with the second letter, and a folder inside is labeled with the third letter. If you want to find "cat", you go to the C cabinet, pull the A drawer, and grab the T folder. If you want "car", you use the exact same C cabinet and A drawer, but look for the R folder instead. The prefix "ca" is shared, saving space and time.

inserting "cat", "car", "dog":

        root
       /    \
      c      d
      |      |
      a      o
     / \     |
    t   r    g
    ●   ●    ●        ● marks the end of a word

"ca" is a real path but has no ●, so it is a prefix and not a stored word. That distinction is why the flag exists.

The flag that makes it work ​

Without a marker, search("ca") and startsWith("ca") would give the same answer, and the structure could not tell a stored word from an intermediate step.

So each node carries is_word. Then:

  • search — walk the characters, then check the flag.
  • startsWith — walk the characters, and stop. The flag is irrelevant.

Those two methods differ by exactly one line, which is the cleanest way to see what the flag is for.

The solution ​

python
class TrieNode:
    def __init__(self):
        self.children = {}          # (1) character → TrieNode
        self.is_word = False  # (2)


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

    def insert(self, word: str) -> None:
        node = self.root  # (4)
        for c in word:
            if c not in node.children:  # (5)
                node.children[c] = TrieNode()
            node = node.children[c]  # (6)
        node.is_word = True  # (7)

    def _walk(self, prefix: str):  # (8)
        node = self.root
        for c in prefix:
            if c not in node.children:
                return None  # (9)
            node = node.children[c]
        return node

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

    def startsWith(self, prefix: str) -> bool:
        return self._walk(prefix) is not None  # (12)
ts
class TrieNode {
  children = new Map<string, TrieNode>();  // (1)
  isWord = false;  // (2)
}

class Trie {
  private root = new TrieNode();  // (3)

  insert(word: string): void {
    let node = this.root;  // (4)
    for (const c of word) {
      if (!node.children.has(c)) node.children.set(c, new TrieNode());  // (5)
      node = node.children.get(c)!;  // (6)
    }
    node.isWord = true;  // (7)
  }

  private walk(prefix: string): TrieNode | null {  // (8)
    let node = this.root;
    for (const c of prefix) {
      const next = node.children.get(c);
      if (!next) return null;  // (9)
      node = next;
    }
    return node;
  }

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

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

Pulling the shared walk into a helper is not just tidiness — it makes the one-line difference between search and startsWith visible, which is exactly what an interviewer wants to see you understand.

Line by line ​

(1) Each node's children, stored in a map from a character to the next node. The map only holds characters that actually come next, so most nodes have just a few entries.

(2) The end-of-word flag. It says "a stored word ends exactly here". It starts False, because most nodes are just steps on the way to longer words.

(3) The root is an empty node. It stands for the empty prefix, before any character.

(4) insert starts at the root.

(5) If the next character has no node yet, create one. This is where new branches grow.

(6) Step down to that character's node. After the loop, node is the node for the last character of the word.

(7) Mark that a word ends here. Without this line, search("cat") could not tell "cat" was stored, rather than only being part of "cats".

(8) A shared helper that walks a string from the root. Both search and startsWith need exactly this walk, so it is written once.

(9) A missing character means no stored word starts with this string. Return None at once.

(10) search walks the whole word.

(11) The path must exist and must end on a node with the flag set. This is the one line where search differs from startsWith.

(12) startsWith only needs the path to exist. The flag does not matter, because a prefix need not be a whole word.

Trace ​

Let's trace insert("cat") and then search("ca").

  1. insert("cat")
    • Start at root.
    • c: not in children. Add it. Move to c node.
    • a: not in children. Add it. Move to a node.
    • t: not in children. Add it. Move to t node.
    • End of word: set t_node.is_word = True.
  2. search("ca")
    • Call _walk("ca").
    • c is in root's children, move to c node.
    • a is in c's children, move to a node.
    • Loop ends. Return a node.
    • In search, node is not None, but node.is_word is False. Return False.

Edge cases ​

  • Searching a prefix of a stored word, like search("ca") after insert("cat"). The path exists but the flag is off, so false. startsWith("ca") is true.
  • Inserting the same word twice. The second insert walks existing nodes and sets the flag again. Nothing changes.
  • One word inside another, like "app" and "apple". Both flags live on the same path, at different depths.
  • The empty string. startsWith("") walks nothing and returns true. search("") is true only if the empty word was inserted.

Map or array for the children? ​

Both are used, and the choice is a real trade.

A 26-slot array is faster — indexing beats hashing — and it makes the code slightly shorter. But every node allocates 26 slots whether it uses them or not, which wastes memory on sparse tries, and it only works for a known small alphabet.

A hash map allocates only what is used and handles any alphabet, including Unicode.

For lowercase English with dense data, the array wins. For anything else, the map. Say which you chose and why — this is the design decision the problem is really testing.

Complexity ​

For a word of length L:

  • insert, search, startsWith — all O(L).

Note what is not in that bound: the number of stored words. A trie's lookup cost depends only on the length of the key, not on how many keys exist. That is the property that makes it useful.

Space is O(\text{total characters}) in the worst case, and much less in practice because shared prefixes are stored once.

Let's break this down:

  • Time Complexity: To insert or search for a word, we step through each of its characters exactly once. For a word of length L, we perform L steps. At each step, we look up a character in a hash map (or index into a 26-slot array), which takes constant O(1) time. Thus, the total time is L \times O(1) = O(L).
  • Space Complexity: Every character in the worst case (e.g., if no words share any prefixes, like "cat" and "dog") requires a new node. If we insert N words of average length L, we could create up to N \times L nodes. Therefore, space complexity is bounded by O(\text{total characters inserted}). In practice, because prefixes are shared, the actual memory footprint is significantly smaller.

Trie or hash set? ​

triehash set
exact lookupO(L)O(L) to hash, then O(1)
prefix queriesO(L)impossible without a full scan
sorted iterationfree, in orderneeds a separate sort
memoryshares prefixesstores every key whole

Use a trie when prefixes matter. For exact membership alone, a hash set is simpler and usually faster.

Where this appears ​

  • Autocomplete — walk to the prefix node, then collect the words below it. Chapter 11.11 builds this as a system.
  • IP routing — a router matches the longest prefix of a destination address, using a trie over bits rather than characters. Chapter 5.3.2.
  • Spell checkers and word games — 4.15.3 Word Search II is the clearest example.
  • Compressed tries (radix trees) — merge chains of single-child nodes into one edge holding a whole string. Far less memory, and it is what real routing tables use. 4.13.4 covers it.

What the interviewer will push on ​

"Why not a hash set?" It cannot answer prefix queries.

"Why does each node need a flag?" To tell a stored word from an intermediate prefix. Give "ca" versus "cat".

"Array or map for the children?" State the memory-versus-speed trade and the alphabet assumption.

"How would you implement delete?" Walk down, clear the flag, then unlink nodes on the way back up only while they have no children and are not word endings. That reverse pass is the interesting part.

"How would you return all words with a prefix?" Walk to the prefix node, then DFS below it collecting every node with the flag set.

One thing to volunteer: point out that the cost depends on key length only, not on how many words are stored. That is the property that justifies the structure.

Next: 4.15.2 Design Add and Search Words — the same trie, with a wildcard that forces the search to branch.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet