--- # === IDENTITY === id: software/patterns/trie-prefix-tree/2026 canonical_question: "How do I implement and use a Trie (prefix tree)?" aliases: - "prefix tree implementation" - "trie data structure insert search delete" - "autocomplete trie algorithm" - "word dictionary prefix lookup" - "trie vs hash map for string search" - "radix tree compressed trie" entity_type: software_reference domain: software > patterns > trie_prefix_tree region: global jurisdiction: global temporal_scope: 1960-2026 # === VERIFICATION === last_verified: 2026-02-24 confidence: 0.95 version: 1.0 first_published: 2026-02-24 # === TEMPORAL VALIDITY === temporal_validity: status: stable last_breaking_change: null next_review: 2026-08-23 change_sensitivity: low # === CONSTRAINTS === constraints: - "Memory usage grows with alphabet size: each node may hold up to |SIGMA| child pointers (26 for lowercase, 128 for ASCII, 1M+ for Unicode)" - "Tries are not cache-friendly due to pointer chasing; for latency-critical paths, consider array-based or DAFSA alternatives" - "Delete operations must not orphan subtrees: always check whether a node still has children before removing it" - "For Unicode strings, use hash-map children (not fixed arrays) to avoid allocating millions of slots per node" # === SKIP CONDITIONS === skip_this_unit_if: - condition: "Need exact-match lookup only, no prefix queries" use_instead: "Use a hash set or hash map for O(1) average-case lookups" - condition: "Strings are very long (>1 KB) and few share prefixes" use_instead: "Use a hash map or suffix array; trie depth equals string length" # === AGENT HINTS === inputs_needed: - key: use_case question: "What is the primary use case for the trie?" type: choice options: ["autocomplete", "spell check", "IP routing (longest prefix match)", "word games (Boggle/Scrabble)", "dictionary lookup", "XOR-based max query"] - key: alphabet_size question: "What character set will keys use?" type: choice options: ["lowercase a-z (26)", "alphanumeric (62)", "ASCII (128)", "Unicode / arbitrary bytes"] # === DISTRIBUTION === canonical_source: "https://knowledgelib.io/software/patterns/trie-prefix-tree/2026" suggested_citation: "Source: knowledgelib.io — AI Knowledge Library (verified 2026-02-24)" # === RELATED UNITS === related_kos: depends_on: [] related_to: - id: "software/patterns/string-matching-kmp-rabin-karp/2026" label: "String Matching: KMP & Rabin-Karp" - id: "software/patterns/graph-algorithms/2026" label: "Graph Algorithms" - id: "software/patterns/bloom-filters/2026" label: "Bloom Filters" solves: [] alternative_to: [] often_confused_with: [] # === SOURCES (7 authoritative sources) === sources: - id: src1 title: "Trie Data Structure" author: GeeksforGeeks url: https://www.geeksforgeeks.org/dsa/trie-insert-and-search/ type: community_resource published: 2024-12-15 reliability: moderate_high - id: src2 title: "Trie" author: Wikipedia url: https://en.wikipedia.org/wiki/Trie type: community_resource published: 2025-01-10 reliability: moderate_high - id: src3 title: "Trie Data Structure: Complete Guide to Prefix Trees" author: Codecademy url: https://www.codecademy.com/article/trie-data-structure-complete-guide-to-prefix-trees type: technical_blog published: 2024-08-20 reliability: moderate_high - id: src4 title: "Implement Trie (Prefix Tree) — LeetCode 208" author: LeetCode url: https://leetcode.com/problems/implement-trie-prefix-tree/ type: community_resource published: 2023-01-01 reliability: high - id: src5 title: "Tries or Prefix Trees" author: Baeldung url: https://www.baeldung.com/cs/tries-prefix-trees type: technical_blog published: 2024-03-15 reliability: moderate_high - id: src6 title: "Time and Space Complexity of Trie" author: OpenGenus url: https://iq.opengenus.org/time-complexity-of-trie/ type: technical_blog published: 2024-06-10 reliability: moderate - id: src7 title: "Advantages of Trie Data Structure" author: GeeksforGeeks url: https://www.geeksforgeeks.org/dsa/advantages-trie-data-structure/ type: community_resource published: 2024-11-05 reliability: moderate_high --- # Trie (Prefix Tree): Complete Reference ## TL;DR - **Bottom line**: A trie provides O(m) insert, search, and prefix-lookup for strings of length m, independent of the total number of stored keys. - **Key tool/command**: `children = {}` (hash-map node) or `children = [None]*26` (fixed-array node) at each trie level. - **Watch out for**: Memory explosion with large alphabets -- use hash-map children instead of fixed-size arrays for anything beyond lowercase a-z. - **Works with**: Any language; no external dependencies. Standard CS data structure since Fredkin (1960). ## Constraints - Memory usage grows with alphabet size: each node may hold up to |SIGMA| child pointers (26 for lowercase, 128 for ASCII, 1M+ for Unicode). - Tries are not cache-friendly due to pointer chasing; for latency-critical paths, consider array-based or DAFSA alternatives. - Delete operations must not orphan subtrees: always check whether a node still has children before removing it. - For Unicode strings, use hash-map children (not fixed arrays) to avoid allocating millions of slots per node. - Trie depth equals the length of the longest key; extremely long keys (e.g., URLs) create deep, thin trees -- consider compressed tries (radix trees) to collapse single-child chains. ## Quick Reference | Operation | Time | Space | Notes | |---|---|---|---| | `insert(word)` | O(m) | O(m) new nodes worst case | m = word length; shared prefixes reuse existing nodes | | `search(word)` | O(m) | O(1) | Returns true only if `is_end` flag is set | | `starts_with(prefix)` | O(p) | O(1) | p = prefix length; checks node existence only | | `delete(word)` | O(m) | O(1) freed per unique suffix node | Must check children before removing nodes bottom-up | | `autocomplete(prefix, k)` | O(p + n) | O(n) | p = prefix length, n = nodes in subtree; DFS/BFS to collect k results | | `longest_prefix(text)` | O(m) | O(1) | Walk trie, track last `is_end` node seen | | `wildcard_search(pattern)` | O(SIGMA^w * m) | O(m) stack | w = number of wildcards; backtracking on '.' or '?' | | `count_prefix(prefix)` | O(p) | O(1) | Requires augmented `count` field at each node | | `XOR maximum` | O(B) | O(N*B) | B = bit width; binary trie for XOR queries | | Compressed trie (radix) | O(m) | ~O(N) total | Collapses single-child chains; fewer nodes, same time | ## Decision Tree ``` START |-- Need prefix-based operations (autocomplete, startsWith, longest prefix)? | |-- YES --> Use a Trie (this unit) | +-- NO | |-- Need only exact-match lookup? | |-- YES --> Use a HashMap / HashSet (O(1) average) | +-- NO | |-- Need sorted iteration of keys? | |-- YES --> Use a sorted array + binary search, or balanced BST | +-- NO | |-- Keys are integers and you need XOR-max queries? | |-- YES --> Use a binary trie (bitwise trie) | +-- NO | |-- Memory is severely constrained and keys share few prefixes? | |-- YES --> Use a HashMap; tries waste memory on sparse trees | +-- NO | +-- DEFAULT --> Trie with hash-map children is a safe general choice ``` ## Step-by-Step Guide ### 1. Implement the TrieNode class Each node holds a mapping from character to child node and a boolean flag indicating end-of-word. [src1] ```python class TrieNode: def __init__(self): self.children = {} # char -> TrieNode self.is_end = False # marks complete word ``` **Verify**: `node = TrieNode(); assert node.children == {} and node.is_end == False` ### 2. Implement insert Walk the trie character by character, creating nodes as needed, and mark the final node. [src1] ```python class Trie: def __init__(self): self.root = TrieNode() def insert(self, word: str) -> None: node = self.root for ch in word: if ch not in node.children: node.children[ch] = TrieNode() node = node.children[ch] node.is_end = True ``` **Verify**: `t = Trie(); t.insert("apple"); assert "a" in t.root.children` ### 3. Implement search and starts_with Search requires `is_end == True` at the final node; starts_with only requires the path exists. [src4] ```python def search(self, word: str) -> bool: node = self._find_node(word) return node is not None and node.is_end def starts_with(self, prefix: str) -> bool: return self._find_node(prefix) is not None def _find_node(self, prefix: str): node = self.root for ch in prefix: if ch not in node.children: return None node = node.children[ch] return node ``` **Verify**: `t.insert("apple"); assert t.search("apple") and not t.search("app") and t.starts_with("app")` ### 4. Implement delete Bottom-up recursive removal: only delete nodes that are not shared with other words. [src5] ```python def delete(self, word: str) -> bool: def _delete(node: TrieNode, word: str, depth: int) -> bool: if depth == len(word): if not node.is_end: return False # word not in trie node.is_end = False return len(node.children) == 0 # can delete if no children ch = word[depth] if ch not in node.children: return False should_delete = _delete(node.children[ch], word, depth + 1) if should_delete: del node.children[ch] return not node.is_end and len(node.children) == 0 return False return _delete(self.root, word, 0) ``` **Verify**: `t.insert("apple"); t.insert("app"); t.delete("apple"); assert t.search("app") and not t.search("apple")` ### 5. Add autocomplete Collect all words under a given prefix using DFS. [src3] ```python def autocomplete(self, prefix: str, limit: int = 10) -> list: node = self._find_node(prefix) if node is None: return [] results = [] def dfs(node, path): if len(results) >= limit: return if node.is_end: results.append(prefix + path) for ch in sorted(node.children): dfs(node.children[ch], path + ch) dfs(node, "") return results ``` **Verify**: `t.insert("app"); t.insert("apple"); t.insert("application"); assert t.autocomplete("app") == ["app", "apple", "application"]` ## Code Examples ### Python: Full Trie with all operations > Full script: [python-full-trie-with-all-operations.py](scripts/python-full-trie-with-all-operations.py) (29 lines) ```python # Input: list of words to insert, queries to search/autocomplete # Output: boolean search results, list of autocomplete suggestions class TrieNode: __slots__ = ('children', 'is_end') # memory optimization def __init__(self): # ... (see full script) ``` ### JavaScript: Trie with autocomplete > Full script: [javascript-trie-with-autocomplete.js](scripts/javascript-trie-with-autocomplete.js) (48 lines) ```javascript // Input: words array, prefix string // Output: array of autocomplete suggestions class TrieNode { constructor() { this.children = new Map(); // char -> TrieNode # ... (see full script) ``` ### Java: Trie with array-based children (lowercase a-z) > Full script: [java-trie-with-array-based-children-lowercase-a-z.java](scripts/java-trie-with-array-based-children-lowercase-a-z.java) (40 lines) ```java // Input: String words, String prefix // Output: boolean for search, List for autocomplete class Trie { private static final int ALPHA = 26; private int[][] children; // node x 26 # ... (see full script) ``` ### Go: Trie with map children > Full script: [go-trie-with-map-children.go](scripts/go-trie-with-map-children.go) (40 lines) ```go // Input: strings to insert, prefix to search // Output: bool for search, []string for autocomplete package trie type TrieNode struct { Children map[byte]*TrieNode # ... (see full script) ``` ## Anti-Patterns ### Wrong: Using fixed array[26] for variable alphabets ```python # BAD -- allocates 26 slots per node even when alphabet is larger or smaller class TrieNode: def __init__(self): self.children = [None] * 26 # breaks for uppercase, digits, Unicode self.is_end = False def insert_char(self, c): idx = ord(c) - ord('a') # IndexError for 'A', '0', etc. if self.children[idx] is None: self.children[idx] = TrieNode() ``` ### Correct: Use a dictionary for flexible alphabets ```python # GOOD -- handles any character set, allocates only for characters present class TrieNode: def __init__(self): self.children = {} # works with any hashable character self.is_end = False ``` ### Wrong: Delete without checking children ```python # BAD -- naively removes node, orphaning words that share the prefix def bad_delete(self, word): node = self.root for ch in word: node = node.children[ch] node.is_end = False # "apple" deleted, but "application" subtree now unreachable? # WRONG: does not check if node has children, may remove shared prefix nodes ``` ### Correct: Bottom-up delete with child check ```python # GOOD -- only removes nodes that have no children and are not end-of-word def delete(self, word): def _del(node, word, d): if d == len(word): if not node.is_end: return False node.is_end = False return len(node.children) == 0 # safe to remove only if leaf ch = word[d] if ch not in node.children: return False should_del = _del(node.children[ch], word, d + 1) if should_del: del node.children[ch] return not node.is_end and len(node.children) == 0 return False _del(self.root, word, 0) ``` ### Wrong: Not using __slots__ or compact representation ```python # BAD -- each TrieNode carries a full __dict__, wasting ~100+ bytes per node class TrieNode: def __init__(self): self.children = {} self.is_end = False # Python adds __dict__ overhead per instance ``` ### Correct: Use __slots__ to reduce per-node memory ```python # GOOD -- __slots__ eliminates __dict__, saving ~60-100 bytes per node class TrieNode: __slots__ = ('children', 'is_end') def __init__(self): self.children = {} self.is_end = False ``` ## Common Pitfalls - **Memory blowup on large alphabets**: A trie with 1M words of average length 10 using `[None]*128` (ASCII) allocates ~1.28 billion slots. Fix: use `dict` or `Map` children to store only occupied slots. [src6] - **Forgetting `is_end` flag**: Inserting "apple" makes "app" traversable but not findable without the end marker. Fix: always check `is_end` in `search()`, not just node existence. [src1] - **Not compressing single-child chains**: A trie storing URLs like `https://example.com/...` creates one node per character in the shared prefix. Fix: use a radix tree (compressed trie) to merge single-child chains into edge labels. [src2] - **Wildcard search without backtracking limit**: Patterns like `...` (all wildcards) degenerate to full-tree DFS. Fix: impose a maximum result count or depth limit. [src4] - **Thread safety with concurrent inserts**: Tries are not inherently thread-safe; concurrent inserts can corrupt the tree. Fix: use a read-write lock or concurrent trie implementation (Ctrie). [src7] - **Case sensitivity mismatch**: Inserting "Apple" but searching "apple" fails. Fix: normalize keys to lowercase (or desired case) before insert and search. [src3] ## When to Use / When Not to Use | Use When | Don't Use When | Use Instead | |---|---|---| | Need autocomplete or prefix search on a dictionary | Only need exact-match key-value lookup | HashMap / HashSet | | Building a spell checker with edit-distance suggestions | Keys are numeric IDs with no prefix relationships | Hash table or array index | | Implementing longest-prefix match (IP routing tables) | Memory is severely constrained and keys share few prefixes | HashMap (lower per-key overhead) | | Need sorted iteration of all keys with a given prefix | Keys are very long (>1 KB) and rarely share prefixes | Sorted array + binary search | | Word game solvers (Boggle, Scrabble) with prefix pruning | Need range queries on numeric keys | Balanced BST or B-tree | | XOR-maximum queries on integers (binary trie) | Dataset is static and fits in a sorted array | Binary search (simpler, cache-friendly) | ## Important Caveats - Tries invented by Fredkin (1960) are a foundational data structure; the concept is stable and not subject to breaking changes. The term "trie" comes from re**trie**val, not "tree." - In practice, hash maps often outperform tries for exact lookups due to better cache locality, even though tries have better worst-case guarantees (O(m) vs O(m) average for hash, O(m*n) worst). - Compressed variants (radix trees, Patricia tries, DAFSA) significantly reduce memory usage but add implementation complexity. Libraries like `datrie` (Python), `art` (Go), or `apache/commons-collections` (Java) provide production-ready implementations. - For competitive programming, array-based tries with pre-allocated nodes are preferred for speed; for production code, hash-map-based tries are preferred for flexibility. ## Related Units - [String Matching: KMP & Rabin-Karp](/software/patterns/string-matching-kmp-rabin-karp/2026) - [Graph Algorithms](/software/patterns/graph-algorithms/2026) - [Bloom Filters](/software/patterns/bloom-filters/2026)