Trie — Core Operations

All three trie operations are the same code — walk the path character by character. insert creates nodes as it walks; search and startsWith just follow them. In fact, search and startsWith differ by exactly one line — and which line that is decides whether "car" counts as a word or merely a prefix. Get that one line and you’ve got the whole chapter.

Three operations, one shared shape: walk the path character by character. insert creates nodes as it goes; search and startsWith just follow existing nodes and report whether the walk succeeds. Once you’ve written one, the others are variations.

Try it first

Insert a few words, then search for an exact word and startsWith a prefix. Watch how search and startsWith differ on a prefix that isn’t itself a word (insert card, then search("car") vs startsWith("car")).

Predict first

The trie holds {cat, car, card, dog, do}. Predict three results: search('car'), startsWith('car'), and search('ca').

Try it — insert words, then search or check a prefix

Words in the trie: cat, car, card, dog, do

The node

The one design decision is how to store children. Two options:

Array of size 26 (children[26]) — for lowercase a–z. O(1) indexing, but every node reserves 26 slots even if it uses one. Fast, memory-heavy.
Hash map (char → node) — allocates only the characters actually used. Slightly slower per step, far less memory for sparse/large alphabets (Unicode, mixed case).

Use the array for a–z interview problems (it’s faster and the alphabet is tiny); use the map when the alphabet is large or sparse.

insert, search, startsWith

Notice all three operations funnel through one walk helper. search adds an isEnd check; startsWith doesn’t. insert is walk that creates missing nodes instead of bailing. That symmetry is worth pointing out in an interview — it shows you see the shared structure.

The one line that splits search from startsWith

Both walk the same path. Fill in the two returns — the isEndOfWord check is the only difference:

python · fill in the blanks0/2 hints

def _walk(self, s):
  cur = self.root
  for c in s:
      if c not in cur.children:
          return None
      cur = cur.children[c]
  return cur
 
def search(self, word):
  node = self._walk(word)
  # ??? what does this operation return?
 
def starts_with(self, prefix):
  # ??? what does this operation return?

Run it yourself

Don’t take the code’s word for it — run it. Edit the words or the queries below and watch how search (exact word) and startsWith (prefix) diverge. Try search("ca") vs startsWith("ca").

Run it yourself — Python

class TrieNode:
  def __init__(self):
      self.children = {}      # char -> TrieNode
      self.is_end = False

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

  def insert(self, word):
      cur = self.root
      for c in word:
          cur = cur.children.setdefault(c, TrieNode())
      cur.is_end = True

  def _walk(self, s):
      cur = self.root
      for c in s:
          if c not in cur.children:
              return None
          cur = cur.children[c]
      return cur

  def search(self, word):
      node = self._walk(word)
      return node is not None and node.is_end

  def starts_with(self, prefix):
      return self._walk(prefix) is not None

t = Trie()
for w in ["cat", "car", "card", "dog", "do"]:
  t.insert(w)

print("search('car')     ->", t.search("car"))
print("search('ca')      ->", t.search("ca"))       # only a prefix, not a word
print("startsWith('ca')  ->", t.starts_with("ca"))
print("search('card')    ->", t.search("card"))
print("startsWith('z')   ->", t.starts_with("z"))

class TrieNode:
  def __init__(self):
      self.children = {}      # char -> TrieNode
      self.is_end = False

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

def insert(self, word):
      cur = self.root
      for c in word:
          cur = cur.children.setdefault(c, TrieNode())
      cur.is_end = True

def _walk(self, s):
      cur = self.root
      for c in s:
          if c not in cur.children:
              return None
          cur = cur.children[c]
      return cur

def search(self, word):
      node = self._walk(word)
      return node is not None and node.is_end

def starts_with(self, prefix):
      return self._walk(prefix) is not None

t = Trie()
for w in ["cat", "car", "card", "dog", "do"]:
  t.insert(w)

print("search('car')     ->", t.search("car"))
print("search('ca')      ->", t.search("ca"))       # only a prefix, not a word
print("startsWith('ca')  ->", t.starts_with("ca"))
print("search('card')    ->", t.search("card"))
print("startsWith('z')   ->", t.starts_with("z"))

Collecting all words under a prefix (autocomplete)

The prefix-query superpower: walk to the prefix node, then DFS the subtree, emitting a word at every isEnd.

This is the engine behind autocomplete. The cost is O(L) to reach the prefix plus O(size of the subtree) to enumerate — you only ever touch words that actually share the prefix.

Deletion (the tricky one)

Deleting is rarely asked but worth knowing. You can’t just unmark isEnd and walk away if you care about memory — you should prune nodes that become useless. The rule:

Walk to the word’s end node; unset `isEnd`

If the path doesn’t fully exist, the word isn’t there — nothing to do.

Prune bottom-up

Going back up, delete a node only if it has no children and is not itself an end-of-word for some other word. Stop pruning the moment you hit a node that’s still needed (it has another child, or marks a shorter word).

⚠️

The deletion trap: never prune a node another word still needs. If you delete do from a trie that also holds dog, you must only clear the is_end flag on the o node — you cannot remove the d→o path, because dog walks through it. Pruning is allowed solely for nodes that become leaves with no end-flag. Get this wrong and you silently delete unrelated words.

Complexity recap

Operation	Time	Notes
`insert`, `search`, `startsWith`	O(L)	L = word length, independent of word count
autocomplete (prefix → all words)	O(L + subtree)	only touches matching words
`delete`	O(L)	plus pruning along the path

Quick check

In the code above, what's the ONLY difference between search(word) and startsWith(word)?

You implement children as an array of 26 pointers per node. What's the main downside versus a hash map?

Why must trie deletion prune nodes bottom-up and stop at the first 'still-needed' node?

You’ve got the three O(L) operations and the one flag that distinguishes them. Next: Variations & Tricks — compressed/radix tries, the bitwise trie that turns the bit tricks from Day 17 into a data structure (and cracks XOR problems), and storing values at nodes.

Introduction Variations & Tricks

Finished this page?