Trie (Prefix Tree)
A tree specialized for prefix search over strings — autocomplete's favorite data structure.
- 1 Lesson
Dry-run engine
Trie Insert
A trie spends 26 pointer slots on every node so that shared prefixes are stored exactly once.
- Input · Insert word
- insert("cap")
- Output · Result
- Press play to run it
How it works
For each character, follow children[ch - 'a']. If that slot is null, allocate a node there. After the last character, mark isEnd = true.
trie_nodes · 26 slots each
- currroot @0x8a00
- i0 → 'c'
- Slotchildren[2] = 0x8a60
- Nodes6
Each trie node reserves 26 child pointers — one per letter — plus an end-of-word flag. insert("cap") starts at the root. i = 0 is 'c': children[2] of the root node already holds 0x8a60, a node shared with "cat" and "cup". Follow it — the prefix "c" costs no new memory.
1 / 4
Course Contents
Related courses
- ArraysContiguous, indexable memory — the foundation almost every other data structure builds on.12 lessons · 16 problems
- StringsCharacter arrays with their own set of classic patterns — two pointers, sliding window, and more.19 lessons · 19 problems
- Linked ListNodes linked one direction by pointers instead of contiguous memory.4 lessons · 12 problems