Implement Trie (Prefix Tree)

TRIE · MEDIUM

The problem

Design a data structure that supports three operations: insert(word) — add a word; search(word) — return true only if that exact word was previously inserted; startsWith(prefix) — return true if any previously inserted word starts with that prefix. All three should stay fast even with many words sharing common prefixes, like "app", "apple", and "application".

LeetCode: Implement Trie (Prefix Tree)

Solution 1: Brute force — a Set of whole words

The simplest thing that could work: keep every inserted word in a Set. insert is trivial. search is a direct membership check. But startsWith has no shortcut — nothing about a Set knows which words share a prefix, so it has to check every single stored word.

Brute force: one flat Set of whole words

┌──────────┐    ┌──────────┐    ┌──────────┐
│ "apple"  │    │ "banana" │    │ "app"    │
└──────────┘    └──────────┘    └──────────┘

search("app") has to check every entry in order — there's no
shortcut for shared prefixes like "apple" and "app".

Cost: O(n × m) per search, where n = word count and m = word length.

Interactive visualization

Searching for "car" in the word list

Press play to scan for a word.

words checked: —

Step 0 / 0

The code

class TrieBruteForce {
  constructor() {
    this.words = new Set();
  }
  insert(word) {
    this.words.add(word);
  }
  search(word) {
    return this.words.has(word);
  }
  startsWith(prefix) {
    for (const w of this.words) {
      if (w.startsWith(prefix)) return true;
    }
    return false;
  }
}

Line by line:

insert is O(word length) — just hashing the string into the Set.
search is a direct Set.has lookup — also fast on its own.
startsWith is the expensive one: it has to loop over every stored word and call .startsWith(prefix) on each, because a flat Set has no structure that groups words by their shared prefixes.

Complexity

insert	search	startsWith	Space
O(m)	O(n × m)	O(n × m)	O(n × m)

Solution 2: Optimal — a Trie of Map nodes

Instead of storing whole words, store one node per character. Words that share a prefix share the same chain of nodes — "app" and "apple" both walk through the same a → p → p nodes before diverging. Each node knows whether it’s the end of a real inserted word via an isWord flag.

Optimal: one Trie node per character, shared prefixes stored once

        •
        |
        a
        |
        p
        | (green = end of a word)
        p ✓
        |
        l
        |
        e ✓

"app" and "apple" share the a-p-p prefix — it's stored once, not once per word.

Cost: O(m) per operation, where m = word/prefix length — independent of word count.

Interactive visualization

Tracing: insert("apple"), search("apple"), search("app"), startsWith("app"), insert("app"), search("app")

Press Play or Step to begin.

Step 0 / 0

This animation traces the exact sequence: insert(“apple”), search(“apple”), search(“app”), startsWith(“app”), insert(“app”), search(“app”).

The code

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch);
    }
    node.isWord = true;
  }
  _walk(str) {
    let node = this.root;
    for (const ch of str) {
      if (!node.children.has(ch)) return null;
      node = node.children.get(ch);
    }
    return node;
  }
  search(word) {
    const node = this._walk(word);
    return node !== null && node.isWord;
  }
  startsWith(prefix) {
    return this._walk(prefix) !== null;
  }
}

Line by line:

insert walks one character at a time, creating a child node only when that character isn’t already there — this is exactly what makes shared prefixes free.
_walk is shared by both search and startsWith — it returns the node reached by following a string’s characters, or null the moment a character has no matching child.
search additionally requires isWord to be true — reaching a node isn’t enough, since that node might only represent a prefix, not a full inserted word (this is the search("app") before insert("app") case).
startsWith only needs the path to exist — it doesn’t care whether the final node is a complete word.

Complexity

insert	search	startsWith	Space
O(m)	O(m)	O(m)	O(total characters across all words, shared prefixes counted once)

Complexity comparison

Solution	insert	search	startsWith
Brute force (Set of words)	O(m)	O(n × m)	O(n × m)
Optimal (Trie, Map children)	O(m)	O(m)	O(m)

Interview corner

Q: Why not just use a Set for everything, given how simple it is?

Set’s startsWith requires scanning every stored word.
Nothing about a Set knows which words share a prefix.
A Trie makes prefix operations proportional to the prefix length (m), not the number of words stored (n).

⚠ Trap: don’t claim a Trie is “always better” — for small datasets, or when only exact search matters and startsWith is never called, a flat Set’s simplicity and lower per-node overhead can win in practice.

Q: How would you delete a word from a Trie?

Walk down to the word’s last node.
Unset that node’s isWord flag.
Walk back up, removing any node that has no children left AND isn’t itself the end of another word.

↳ Common follow-up: “What if the word being deleted is itself a prefix of another word?” Then you only unset isWord — no nodes get deleted, since the chain is still needed by the longer word.

Q: What’s the space tradeoff of a Trie vs. a Set for a large dictionary?

A Trie can use more memory than a flat Set when words don’t share many prefixes — each node carries overhead beyond just its character, a whole Map object.
A Trie uses far less memory when there’s heavy prefix sharing, like an autocomplete dictionary or a phone contacts list.
It’s a data-dependent tradeoff, not a universal win either way.

Q: Trick question — what does this log?

const m = new Map();
m.set("a", { note: "original subtree" });
m.set("a", {});
console.log(m.get("a"));
console.log(m.size);

Answer: {}, then 1.
Map.set on an existing key overwrites the value — it does not add a second entry.
The original { note: "original subtree" } object is gone, replaced entirely by {}.

⚠ Trap: this is exactly why insert above checks if (!node.children.has(ch)) before calling node.children.set(ch, new TrieNode()) — skipping that check and always calling set would silently blow away an existing child’s entire subtree every time a shared prefix gets inserted again.

Quiz

1. Why does the brute-force Set approach get slower as more words are added, even for a single search?

It has no shared-prefix structure, so it scans stored words one at a time
It doesn’t — Set lookups are always O(1) regardless of word count
Sets keep words in sorted order, which slows lookups down

2. What does each Trie node’s isWord flag mean?

The path to this node spells out a complete inserted word
This node has at least one child
This node is the root of the trie

3. Why doesn’t inserting “app” after “apple” create 3 new nodes?

The a-p-p prefix chain already exists from inserting “apple” — it’s reused
“app” is ignored because it’s shorter than an existing word
Tries automatically deduplicate every operation regardless of characters

4. search("app") and startsWith("app") both walk the same 3 nodes (a, p, p). What’s the one difference between them?

search additionally checks the final node’s isWord flag
search doesn’t walk the tree at all
startsWith is always faster because it stops early

5. What’s the time complexity of the optimal Trie’s insert/search, in terms of word length m and word count n?

O(m) — independent of n
O(n × m) — same as the brute force
O(log n)