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.
⌨ 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 (LeetCode 208) — Iterative ───
# Pattern: Character-indexed children — ord(c)-97
# Time: O(m) per op Space: O(n)
#
# 1. TrieNode: children = [None]*26, end = False
#
# 2. insert: node = self.root; for c in word: idx = ord(c)-97; create child if None; node = node.children[idx]; node.end = True
#
# 3. search: node = self._traverse(word); return node is not None and node.end
#
# 4. startsWith: return self._traverse(prefix) is not None
#
# 5. _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
#
# Vars: node, idx, c
▼ your implementation ▼
Verify your solution:
⌨ Type It — Recursive Trie
Practice until you don't need to look. Recursive versions use helper functions.
# ─── TRIE (LeetCode 208) — Recursive ───
# insert: _insert(node, word, i) — base: i==len(word) → node.end=True