Trie (Prefix Tree)
A Trie (pronounced 'try'), also called a prefix tree or digital tree, is a tree-based data structure for storing strings where each path from root to leaf represents a word. Each node stores a character, and paths share common prefixes. Invented by Edward Fredkin in 1960, tries enable O(m) time complexity for insert, search, and prefix operations where m is the string length. Essential for autocomplete, spell checking, IP routing, and dictionary implementations.
Visualization
Interactive visualization for Trie (Prefix Tree)
Interactive visualization with step-by-step execution
Implementation
1class TrieNode {
2 children: Map<string, TrieNode> = new Map();
3 isEndOfWord: boolean = false;
4}
5
6class Trie {
7 private root: TrieNode = new TrieNode();
8
9 insert(word: string): void {
10 let node = this.root;
11 for (const char of word) {
12 if (!node.children.has(char)) {
13 node.children.set(char, new TrieNode());
14 }
15 node = node.children.get(char)!;
16 }
17 node.isEndOfWord = true;
18 }
19
20 search(word: string): boolean {
21 let node = this.root;
22 for (const char of word) {
23 if (!node.children.has(char)) return false;
24 node = node.children.get(char)!;
25 }
26 return node.isEndOfWord;
27 }
28
29 startsWith(prefix: string): boolean {
30 let node = this.root;
31 for (const char of prefix) {
32 if (!node.children.has(char)) return false;
33 node = node.children.get(char)!;
34 }
35 return true;
36 }
37}Deep Dive
Theoretical Foundation
Trie stores strings character by character in tree nodes. The root is empty, each edge represents a character, and paths from root spell out strings. Each node has up to 26 children (for lowercase English) or 256 (ASCII). A boolean flag marks word endings. Unlike hash tables, tries provide prefix-based operations efficiently. They use more memory but excel at prefix matching, autocomplete, and sorted iteration. Space-time tradeoff: O(ALPHABET_SIZE × N × M) space for N strings of average length M, but O(M) operations regardless of dataset size.
Complexity
Time
O(m)
O(m)
O(m)
Space
O(n * m)
Applications
Industry Use
Autocomplete features (Google search, IDEs)
Spell checkers and auto-correction
IP routing tables (longest prefix matching)
T9 predictive text on phones
Dictionary implementations
Genome sequence analysis
Contact name search in phones
Browser history and URL suggestions
Use Cases
Related Algorithms
Binary Search Tree (BST)
A hierarchical data structure where each node has at most two children, maintaining the property that all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This ordering property enables efficient O(log n) operations on average for search, insert, and delete. BSTs form the foundation for many advanced tree structures and are fundamental in computer science.
Stack
LIFO (Last-In-First-Out) data structure with O(1) push/pop operations. Stack is a fundamental linear data structure where elements are added and removed from the same end (top). It's essential for function calls, expression evaluation, backtracking algorithms, and undo operations in applications.
Queue
FIFO (First-In-First-Out) data structure with O(1) enqueue/dequeue operations. Queue is a fundamental linear data structure where elements are added at one end (rear) and removed from the other end (front). Essential for breadth-first search, task scheduling, and buffering systems.
Hash Table (Hash Map)
A data structure that implements an associative array abstract data type, mapping keys to values using a hash function. Hash tables provide O(1) average-case time complexity for insertions, deletions, and lookups, making them one of the most efficient data structures for key-value storage. The hash function computes an index into an array of buckets from which the desired value can be found.