1. Introduction to Tries (Prefix Trees)
A Trie (pronounced "try", derived from the word retrieval), also commonly referred to as a Prefix Tree or Digital Tree, is an N-ary tree data structure used to store and search collections of strings over a shared alphabet.
Unlike a Binary Search Tree, where each node stores a full key, a Trie node's position within the tree hierarchy defines the key associated with it. All child descendants of a node share the common string prefix associated with that parent node.
+─────────────────────────────────────────────────────────────────────────────+
| PREFIX TREE (TRIE) STRUCTURE |
+─────────────────────────────────────────────────────────────────────────────+
Stored Dictionary: ["cat", "car", "cart", "dog", "dot"]
(Root Node)
/ \
[ 'c' ] [ 'd' ]
| |
[ 'a' ] [ 'o' ]
/ \ / \
[ 't'*] [ 'r'*][ 'g'*][ 't'*]
|
[ 't'*]
(* Asterisk denotes isEndOfWord = true)
2. Why Use a Trie Over a Hash Table?
While a Hash Table offers O(L) average lookup for exact string matches (where L is string length), a Trie provides unmatched architectural advantages for prefix-based operations:
+─────────────────────────────────────────────────────────────────────────────+
| HASH TABLE VS TRIE COMPARISON |
+─────────────────────────────────────────────────────────────────────────────+
Feature Hash Table Trie (Prefix Tree)
─────────────────────────────────────────────────────────────────────────────
Exact Match Search (`search`) O(L) O(L)
Prefix Match (`startsWith`) O(N * L) [Full Scan!] O(L) [Instant!]
Autocomplete Suggestions O(N * L log N) O(Prefix + Matches)
Lexicographical (Alphabetical) Unordered Naturally Sorted
Longest Prefix Matching (IP) Slow O(L)
Collisions / Hash DoS Possible Impossible (Deterministic)
Where Tries Power Production Systems:
- Search Engine Autocomplete: Google, Amazon, and browser URL bars use tries to suggest query completions in under 5 milliseconds.
- Spell Checkers & Predictive Text: Mobile keyboards (T9 / SwiftKey) query dictionary tries to suggest auto-corrections.
- Network IP Routing (CIDR Tables): Core routers use longest-prefix-match tries to forward packets to destination IP subnets.
- DNA Bioinformatics: Indexing genomic sequences over the 4-character alphabet
{A, C, G, T}. - Bitwise Maximum XOR Engines: Competitive programming and cryptography algorithms use 32-bit binary tries.
3. TrieNode Anatomy & Memory Models
+─────────────────────────────────────────────────────────────────────────────+
| TRIENODE LAYOUTS |
+─────────────────────────────────────────────────────────────────────────────+
Model A: Fixed Array (Fastest, High Memory)
┌────────────────────────────────────────────────────────┐
│ isEndOfWord: boolean (true/false) │
│ children: TrieNode*[26] (Index 0='a', ..., Index 25='z')│
└────────────────────────────────────────────────────────┘
Model B: Hash Map (Memory Efficient for Sparse Alphabets like Unicode)
┌────────────────────────────────────────────────────────┐
│ isEndOfWord: boolean │
│ children: Map<char, TrieNode*> │
└────────────────────────────────────────────────────────┘
4. Multi-Language Implementations & Syntax
C++ (Trie Class Implementation)
cpp#include <iostream> #include <string> #include <vector> class TrieNode { public: TrieNode* children[26]; bool isEndOfWord; TrieNode() { isEndOfWord = false; for (int i = 0; i < 26; i++) children[i] = nullptr; } }; class Trie { private: TrieNode* root; public: Trie() { root = new TrieNode(); } void insert(const std::string& word) { TrieNode* curr = root; for (char ch : word) { int idx = ch - 'a'; if (!curr->children[idx]) { curr->children[idx] = new TrieNode(); } curr = curr->children[idx]; } curr->isEndOfWord = true; } bool search(const std::string& word) { TrieNode* curr = root; for (char ch : word) { int idx = ch - 'a'; if (!curr->children[idx]) return false; curr = curr->children[idx]; } return curr != nullptr && curr->isEndOfWord; } bool startsWith(const std::string& prefix) { TrieNode* curr = root; for (char ch : prefix) { int idx = ch - 'a'; if (!curr->children[idx]) return false; curr = curr->children[idx]; } return true; } };
Java (Trie Class)
javapublic class Trie { private static class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isEndOfWord = false; } private final TrieNode root; public Trie() { root = new TrieNode(); } public void insert(String word) { TrieNode curr = root; for (int i = 0; i < word.length(); i++) { int idx = word.charAt(i) - 'a'; if (curr.children[idx] == null) { curr.children[idx] = new TrieNode(); } curr = curr.children[idx]; } curr.isEndOfWord = true; } public boolean search(String word) { TrieNode node = findNode(word); return node != null && node.isEndOfWord; } public boolean startsWith(String prefix) { return findNode(prefix) != null; } private TrieNode findNode(String str) { TrieNode curr = root; for (int i = 0; i < str.length(); i++) { int idx = str.charAt(i) - 'a'; if (curr.children[idx] == null) return null; curr = curr.children[idx]; } return curr; } }
Python (Trie Class)
pythonclass TrieNode: def __init__(self): self.children = {} self.is_end_of_word = False class Trie: def __init__(self): self.root = TrieNode() def insert(self, word: str) -> None: curr = self.root for char in word: if char not in curr.children: curr.children[char] = TrieNode() curr = curr.children[char] curr.is_end_of_word = True def search(self, word: str) -> bool: curr = self.root for char in word: if char not in curr.children: return False curr = curr.children[char] return curr.is_end_of_word def starts_with(self, prefix: str) -> bool: curr = self.root for char in prefix: if char not in curr.children: return False curr = curr.children[char] return True
JavaScript (Trie Class)
javascriptclass TrieNode { constructor() { this.children = {}; this.isEndOfWord = false; } } class Trie { constructor() { this.root = new TrieNode(); } insert(word) { let curr = this.root; for (const char of word) { if (!curr.children[char]) { curr.children[char] = new TrieNode(); } curr = curr.children[char]; } curr.isEndOfWord = true; } search(word) { let curr = this.root; for (const char of word) { if (!curr.children[char]) return false; curr = curr.children[char]; } return curr.isEndOfWord; } startsWith(prefix) { let curr = this.root; for (const char of prefix) { if (!curr.children[char]) return false; curr = curr.children[char]; } return true; } }
5. Time & Space Complexity Breakdown
| Operation | Time Complexity | Auxiliary Space |
|---|---|---|
insert(word) | O(L) (where L = word length) | O(L · Sigma) (where Sigma = alphabet size) |
search(word) | O(L) | O(1) |
startsWith(prefix) | O(P) (where P = prefix length) | O(1) |
delete(word) | O(L) | O(1) |
6. Advanced Pattern: Bitwise Trie (Maximum XOR)
Problem Statement: Given an integer array nums, return the maximum result of nums[i] XOR nums[j].
Step-by-Step Logic:
- Every 32-bit integer can be represented as a binary string of 31 bits (
0s and1s). - Insert each number into a Bitwise Binary Trie where children are only
0and1. - To maximize XOR for a number
num, at each bit position from bit 30 down to 0, greedily traverse the opposite bit (1 - currentBit) if it exists in the Trie.
cpp#include <vector> #include <algorithm> struct BinaryTrieNode { BinaryTrieNode* children[2] = {nullptr, nullptr}; }; class Solution { private: BinaryTrieNode* root = new BinaryTrieNode(); void insert(int num) { BinaryTrieNode* curr = root; for (int i = 31; i >= 0; i--) { int bit = (num >> i) & 1; if (!curr->children[bit]) { curr->children[bit] = new BinaryTrieNode(); } curr = curr->children[bit]; } } int findMaxXOR(int num) { BinaryTrieNode* curr = root; int maxVal = 0; for (int i = 31; i >= 0; i--) { int bit = (num >> i) & 1; int oppositeBit = 1 - bit; if (curr->children[oppositeBit]) { maxVal |= (1 << i); curr = curr->children[oppositeBit]; } else { curr = curr->children[bit]; } } return maxVal; } public: int findMaximumXOR(std::vector<int>& nums) { for (int num : nums) insert(num); int globalMax = 0; for (int num : nums) { globalMax = std::max(globalMax, findMaxXOR(num)); } return globalMax; } };
- Time Complexity: O(32 × N) = O(N) — Linear in array size!
- Space Complexity: O(32 × N) = O(N) Trie storage.
7. Compressed Tries (Radix Trees / PATRICIA)
In standard Tries, single-child chains (like r -> o -> a -> d) waste memory nodes. A Radix Tree (Compressed Trie) merges chains of single-child nodes into single composite edge strings:
Standard Trie: (root) ── 'r' ──> [ ] ── 'o' ──> [ ] ── 'a' ──> [ ] ── 'd' ──> [word*]
Radix Tree: (root) ────────── "road" ──────────> [word*]
This reduces node allocations by up to 70% and powers Linux kernel routing tables.
8. Common Pitfalls & Traps
- Forgetting
isEndOfWordFlag: Without this flag, searching for"car"in a trie containing only"cart"would incorrectly returntrue. - Alphabet Indexing Assumptions:
ch - 'a'only works for lowercase English. If uppercase, digits, or unicode strings are stored, use a Hash Map inside eachTrieNode. - Memory Leaks on Deletion: When deleting words in C++, prune orphaned child nodes bottom-up to prevent memory leaks.
9. Frequently Asked Questions (FAQ)
Q1: Why is Trie lookup O(L) and not O(N)?
A: In a Trie, each character of the search string corresponds to exactly one node transition. For a word of length L, we perform at most L pointer dereferences, completely independent of how many millions of words (N) are stored in the tree.
Q2: How does a Trie save memory compared to storing strings in a set?
A: When many strings share prefixes (such as dictionary words starting with "inter-", "anti-", "pre-"), the shared prefix characters are stored exactly once in common ancestor nodes rather than duplicated across every string.
Q3: What is a Bitwise Trie?
A: A Bitwise Trie is a binary trie (branching factor 2: bit 0 and bit 1) used to store the binary representations of integers. It enables O(32) = O(1) queries for maximum/minimum XOR pairs and prefix IP lookups.
Q4: When should I choose a Hash Map over a Trie?
A: Choose a Hash Map if you only need exact string equality lookups and do not require prefix searches, autocomplete suggestions, or alphabetical sorting.
Q5: What is a Radix Tree (Compressed Trie)?
A: A Radix Tree is an optimized Trie where all non-branching node paths are compacted into single edges with multi-character substrings, dramatically reducing tree height and memory footprint.
Q6: Can a Trie be used to search for suffixes?
A: Yes! By inserting strings in reverse (or building a specialized Suffix Tree), a Trie can perform instantaneous suffix matching and substring searches in linear time.