Implement Trie with insert, search, and startsWith.
Each node has 26 children (a–z). end marks word boundaries.
Input: insert("apple"), insert("app") → search("apple")=true, startsWith("ap")=true
InsertO(m)m = word length
SearchO(m)follow path
SpaceO(n·m)n words, avg len m
Step0/12
root (empty)
Ready
Press Play or Step to watch insert("apple") build the trie.
Each character: idx = ord(c) - 97; create child if None; traverse.
InsertO(m)m = word length
SearchO(m)follow path
SpaceO(n·m) + O(m)trie + call stack
Key insight
Recursive: Base case at empty string. Recurse on word[1:] with node.children[idx].
Same O(m) per operation; recursion uses O(m) call stack.
✎ Whiteboard
3
⌨ Type It — Iterative Trie
Practice until you don't need to look. Use the guide comments below as scaffolding. The green highlights are the nuances to burn into memory.
═══ TRIE — ITERATIVE ═══
PATTERN ▸ Character-indexed children (ord(c)-97) O(m) · O(n)
① TRIENODE
children = [None]*26
end = False
② INSERT
node = self.root
for c in word: idx = ord(c)-97; create child if None; node = node.children[idx]
node.end = True
③ SEARCH & STARTSWITH
node = self._traverse(word); return node is not None and node.end
startsWith: return self._traverse(prefix) is not None
④ _TRAVERSE
node = self.root; for c in s: idx = ord(c)-97; if node.children[idx] is None: return None; node = node.children[idx]; return node
▼ your implementation ▼
Verify your solution:
⌨ Type It — Recursive Trie
Practice until you don't need to look. Recursive versions use helper functions.