Trie (Prefix Tree) Data Structure
A Trie (Prefix Tree) is an $N$-ary tree structure designed for fast character prefix string searching, powering search engine autocomplete systems.
Trie Word Insertion Step-by-Step
Branch Character 'c'
Start at Root node. Check root.children['c']. If null, create new TrieNode for letter 'c'.
Root -> Node('c')Branch Character 'a'
Move to Node('c'). Check Node('c').children['a']. Create new TrieNode for letter 'a'.
Root -> Node('c') -> Node('a')Branch Character 't' and Set isEnd Flag
Move to Node('a'). Create Node('t') and set isEnd = true to mark end of word 'cat'.
Root -> Node('c') -> Node('a') -> Node('t') (isEnd = true)Real-world analogy: Dictionary Index Paths
To find 'cat', you follow letter branch 'c', then branch 'a', then branch 't'. Words sharing the same prefix share the same tree path.
- Prefix Branching= Each node contains children references for letters 'a' through 'z'.
Operations explained
Complexity analysis
~9 steps (Logarithmic)
O(log N) Tree Height Time
O(N) Tree Nodes Space
Memory growth rate as N expands.
Relative efficiency rating for large N.
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Search Word / Prefix | O(L) | O(1) |
| Insert Word | O(L) | O(L) |
Code implementations
class TrieNode {
constructor() { this.children = {}; this.isEnd = false; }
}Real-world applications
Search Autocomplete
Suggests query completions as users type letters.
Spell Checking
Validates dictionary words rapidly.
Interview questions
Topic Knowledge Test & Assessment
Trie Knowledge & Skill Test
Validate your conceptual understanding, operation mechanics, and core concepts of Trie.
Topic Metadata
Trie search time depends ONLY on the string length (L), completely independent of how many millions of total words are stored!