🌳 Trie Fundamentals

🎯 What is a Trie?

A Trie (also called a prefix tree) is a tree-based data structure used to store a dynamic set of strings. It's optimized for prefix-based operations and is widely used in autocomplete, spell-checking, and IP routing.

Name: Derived from "retrieval"
Structure: Each node represents a character, path from root forms a string
Key Property: All descendants of a node share a common prefix
Operations: Insert, Search, Delete, Prefix Search

📌 Prefix-Based📌 O(L) Operations📌 Space-Efficient for Shared Prefixes

The Core Insight

Key Insight: Tries store strings character by character, sharing common prefixes. This makes them extremely efficient for prefix-based queries and operations.

Comparison with Hash Table:

Trie O(L) search, supports prefix queries, ordered
Hash Table O(1) search, no prefix support, unordered

# Trie Node Structure
class TrieNode:
    def __init__(self):
        self.children = {}  # Character -> TrieNode
        self.is_end = False  # Marks end of a word
        self.value = None  # Optional: store additional data

# Trie Structure Visualization
# Words: "cat", "car", "dog"
#
#        root
#       /    \
#      c      d
#     / \      \
#    a   a      o
#   /     \      \
#  t       r      g
# (end)   (end)  (end)
#
# Path: root -> c -> a -> t = "cat"

📝 Insert Operation

🎯 Adding a Word to the Trie

Insertion involves traversing the trie character by character, creating nodes as needed, and marking the end of the word.

Approach: Start at root, for each character, go to child or create
Time: O(L) where L is the length of the word
Space: O(L) for new nodes (amortized)
Edge Cases: Empty string, duplicate insertion

# Insert Operation
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

# Example
trie = Trie()
trie.insert("cat")
trie.insert("car")
trie.insert("dog")

# After insertion:
# root -> c -> a -> t (end)
#              -> r (end)
#      -> d -> o -> g (end)

# Step-by-step for "cat":
# 1. Start at root
# 2. 'c' not in root.children → create new node
# 3. Move to 'c' node
# 4. 'a' not in 'c'.children → create new node
# 5. Move to 'a' node
# 6. 't' not in 'a'.children → create new node
# 7. Move to 't' node
# 8. Mark t.is_end = True

🔍 Search Operation

🎯 Checking if a Word Exists

Search traverses the trie following the characters of the word. If all characters exist and the final node is marked as an end, the word exists.

Approach: Traverse character by character
Time: O(L) where L is the length of the word
Returns: True if word exists, False otherwise
Prefix Check: Search doesn't require the final node to be an end

# Search Operation
def search(self, word):
    node = self.root
    for char in word:
        if char not in node.children:
            return False
        node = node.children[char]
    return node.is_end

# Prefix Search (check if any word starts with prefix)
def starts_with(self, prefix):
    node = self.root
    for char in prefix:
        if char not in node.children:
            return False
        node = node.children[char]
    return True

# Example
trie = Trie()
trie.insert("cat")
trie.insert("car")
trie.insert("dog")

print(trie.search("cat"))    # True
print(trie.search("can"))    # False
print(trie.starts_with("ca")) # True
print(trie.starts_with("do")) # True
print(trie.starts_with("x"))  # False

# Search "cat":
# root -> 'c' exists -> 'a' exists -> 't' exists -> node.is_end = True ✓

# Search "can":
# root -> 'c' exists -> 'a' exists -> 'n' doesn't exist ✗

🔤 Prefix Search & Autocomplete

🎯 Finding All Words with a Given Prefix

This is where tries shine! Find all words that start with a given prefix. This is the foundation of autocomplete systems.

Approach: Traverse to the prefix node, then DFS from there
Time: O(P + K) where P = prefix length, K = number of completions
Use Case: Autocomplete, spell-checking, dictionary lookup

# Prefix Search & Autocomplete
def autocomplete(self, prefix):
    # Find the node representing the prefix
    node = self.root
    for char in prefix:
        if char not in node.children:
            return []  # No words with this prefix
        node = node.children[char]
    
    # DFS to find all words from this node
    results = []
    self._dfs(node, prefix, results)
    return results

def _dfs(self, node, current_word, results):
    if node.is_end:
        results.append(current_word)
    
    for char, child in node.children.items():
        self._dfs(child, current_word + char, results)

# Enhanced version with word counts (for ranking)
class TrieWithCount:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.count = node.count + 1  # Track count of words passing through
        node.is_end = True
    
    def autocomplete_with_count(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        
        results = []
        self._dfs_with_count(node, prefix, results)
        return sorted(results, key=lambda x: x[1], reverse=True)  # Sort by count
    
    def _dfs_with_count(self, node, current_word, results):
        if node.is_end:
            results.append((current_word, node.count))
        for char, child in node.children.items():
            self._dfs_with_count(child, current_word + char, results)

# Example
trie = TrieWithCount()
words = ["cat", "car", "cart", "dog", "dodge", "care", "carpet"]
for word in words:
    trie.insert(word)

print(trie.autocomplete("ca"))
# ['car', 'cart', 'cat', 'care', 'carpet'] (sorted by frequency)

🗑️ Delete Operation

🎯 Removing a Word from the Trie

Deletion requires removing the word while cleaning up nodes that are no longer needed.

Approach: Recursive delete, remove nodes with no children
Time: O(L) where L is the length of the word
Key: Only remove nodes that aren't part of other words
Edge Cases: Word is prefix of another word

# Delete Operation
def delete(self, word):
    def _delete(node, word, depth):
        if depth == len(word):
            # Found the end of the word
            if not node.is_end:
                return False  # Word doesn't exist
            node.is_end = False
            # If node has no children, it can be removed
            return len(node.children) == 0
        
        char = word[depth]
        if char not in node.children:
            return False  # Word doesn't exist
        
        child = node.children[char]
        should_delete_child = _delete(child, word, depth + 1)
        
        if should_delete_child:
            del node.children[char]
            # If node has no other children and is not the end of a word
            return len(node.children) == 0 and not node.is_end
        
        return False
    
    _delete(self.root, word, 0)

# Example
trie = Trie()
trie.insert("cat")
trie.insert("car")
trie.insert("cart")

print(trie.search("cat"))   # True
trie.delete("cat")
print(trie.search("cat"))   # False
print(trie.search("car"))   # True (still exists)

# After deleting "cat":
# root -> c -> a -> t (removed, not end of any word)
#              -> r (end)
#                 -> t (end) - "cart"

# Deleting "cart":
# root -> c -> a -> r (end, no children) -> removed
# Result: "car" and "cat" both removed (if no other words)

💻 Full Implementation

🎯 Complete Trie with All Operations

A complete implementation with all standard trie operations, including insert, search, prefix search, delete, and autocomplete.

# Complete Trie Implementation
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
        self.count = 0  # Number of words passing through
        self.value = None  # Optional value storage

class Trie:
    def __init__(self):
        self.root = TrieNode()
        self.size = 0
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.count += 1
        if not node.is_end:
            node.is_end = True
            self.size += 1
    
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end
    
    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True
    
    def autocomplete(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        
        results = []
        self._dfs(node, prefix, results)
        return results
    
    def _dfs(self, node, current, results):
        if node.is_end:
            results.append(current)
        for char, child in sorted(node.children.items()):
            self._dfs(child, current + char, results)
    
    def delete(self, word):
        def _delete(node, word, depth):
            if depth == len(word):
                if not node.is_end:
                    return False
                node.is_end = False
                self.size -= 1
                return len(node.children) == 0
            
            char = word[depth]
            if char not in node.children:
                return False
            
            child = node.children[char]
            should_delete = _delete(child, word, depth + 1)
            
            if should_delete:
                del node.children[char]
                return len(node.children) == 0 and not node.is_end
            
            return False
        
        _delete(self.root, word, 0)
    
    def count_words_with_prefix(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return 0
            node = node.children[char]
        return node.count
    
    def get_all_words(self):
        results = []
        self._dfs(self.root, "", results)
        return results

# Example Usage
trie = Trie()
words = ["apple", "app", "ape", "application", "appetite", "banana"]
for word in words:
    trie.insert(word)

print(trie.search("app"))  # True
print(trie.starts_with("app"))  # True
print(trie.autocomplete("app"))  # ['app', 'ape', 'apple', 'appetite', 'application']
print(trie.count_words_with_prefix("app"))  # 5
print(trie.get_all_words())  # ['app', 'ape', 'apple', 'appetite', 'application', 'banana']

📊 Compressed Trie (Radix Tree)

🎯 Space-Optimized Trie

A compressed trie (also called a radix tree) merges nodes with single children to save space. This is more memory-efficient for large datasets.

Compression: Merge unary paths into single edges
Space: O(n) where n = number of words
Time: O(L) search, slightly slower due to string comparisons
Use Case: IP routing, large dictionaries

# Compressed Trie (Radix Tree) Node
class RadixNode:
    def __init__(self):
        self.children = {}  # key -> child (key is the path string)
        self.is_end = False
        self.value = None

class RadixTree:
    def __init__(self):
        self.root = RadixNode()
    
    def insert(self, word):
        node = self.root
        i = 0
        while i < len(word):
            # Find matching prefix
            matched = False
            for key in list(node.children.keys()):
                # Find common prefix between key and word[i:]
                common = self._common_prefix(key, word[i:])
                if common:
                    if common == key:
                        # Full match - go to child
                        node = node.children[key]
                        i += len(key)
                        matched = True
                        break
                    else:
                        # Partial match - split node
                        # Create new node with common prefix
                        new_node = RadixNode()
                        node.children[common] = new_node
                        # Move remaining part of key to child
                        remaining = key[len(common):]
                        # Copy children and end marker
                        old_node = node.children[key]
                        del node.children[key]
                        new_node.children[remaining] = old_node
                        new_node.is_end = old_node.is_end
                        # Update remaining word suffix
                        node = new_node
                        i += len(common)
                        matched = True
                        break
            
            if not matched:
                # No match - create new node
                node.children[word[i:]] = RadixNode()
                node = node.children[word[i:]]
                i = len(word)
        
        node.is_end = True
    
    def _common_prefix(self, a, b):
        i = 0
        while i < min(len(a), len(b)) and a[i] == b[i]:
            i += 1
        return a[:i] if i > 0 else ""

# Example
radix = RadixTree()
words = ["apple", "app", "ape", "application"]
for word in words:
    radix.insert(word)

# Compressed tree:
# root -> "app" -> "le" (end)
#                 "e" (end)
#                 "lication" (end)
# This saves space compared to uncompressed trie

🌿 Ternary Search Tree

🎯 Memory-Efficient Alternative

A Ternary Search Tree (TST) is a hybrid between a binary search tree and a trie. Each node has three children: left (less), middle (equal), right (greater).

Structure: Each node stores a character, left/mid/right pointers
Space: O(n) memory (good for sparse data)
Time: O(L) average, O(L log n) worst
Use Case: When memory is limited

# Ternary Search Tree
class TSTNode:
    def __init__(self, char):
        self.char = char
        self.left = None
        self.mid = None
        self.right = None
        self.is_end = False

class TernarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self, word):
        self.root = self._insert(self.root, word, 0)
    
    def _insert(self, node, word, idx):
        char = word[idx]
        
        if node is None:
            node = TSTNode(char)
        
        if char < node.char:
            node.left = self._insert(node.left, word, idx)
        elif char > node.char:
            node.right = self._insert(node.right, word, idx)
        else:
            if idx + 1 == len(word):
                node.is_end = True
            else:
                node.mid = self._insert(node.mid, word, idx + 1)
        
        return node
    
    def search(self, word):
        return self._search(self.root, word, 0)
    
    def _search(self, node, word, idx):
        if node is None:
            return False
        
        char = word[idx]
        
        if char < node.char:
            return self._search(node.left, word, idx)
        elif char > node.char:
            return self._search(node.right, word, idx)
        else:
            if idx + 1 == len(word):
                return node.is_end
            return self._search(node.mid, word, idx + 1)

# Comparison: TST vs Trie
# TST: Less memory, good for sparse data
# Trie: Faster, better for dense data

🔤 Suffix Tree & Suffix Array

🎯 Advanced String Indexing Structures

Suffix trees and suffix arrays are powerful data structures for string processing, built on the concept of tries.

Suffix Tree: Compressed trie of all suffixes of a string
Suffix Array: Array of all suffixes in lexicographic order
Time: O(n) or O(n log n) to build
Applications: String matching, longest common substring, bioinformatics

# Suffix Array Construction (Simplified)
def build_suffix_array(text):
    # Add sentinel character
    text = text + '$'
    n = len(text)
    
    # Create all suffixes
    suffixes = [(text[i:], i) for i in range(n)]
    
    # Sort suffixes
    suffixes.sort(key=lambda x: x[0])
    
    # Return suffix array (indices)
    return [idx for _, idx in suffixes]

# Suffix Tree (Conceptual)
# A suffix tree is a compressed trie of all suffixes
# For "banana$":
# Suffixes: banana$, anana$, nana$, ana$, na$, a$
# Suffix Tree contains all these suffixes in compressed form

# Applications:
# 1. Pattern matching: O(m) where m = pattern length
# 2. Longest common substring
# 3. Longest repeated substring
# 4. Find all occurrences of a pattern

def longest_repeated_substring(text):
    # Find longest repeated substring using suffix array
    suffix_array = build_suffix_array(text)
    # Find longest common prefix between adjacent suffixes
    n = len(text)
    max_len = 0
    max_idx = 0
    
    for i in range(len(suffix_array) - 1):
        # Get LCP of adjacent suffixes
        s1 = text[suffix_array[i]:]
        s2 = text[suffix_array[i+1]:]
        lcp = 0
        while lcp < min(len(s1), len(s2)) and s1[lcp] == s2[lcp]:
            lcp += 1
        if lcp > max_len:
            max_len = lcp
            max_idx = suffix_array[i]
    
    return text[max_idx:max_idx + max_len] if max_len > 0 else ""

# Example
text = "banana"
print(longest_repeated_substring(text))  # "ana"

⚡ Bitwise Trie

🎯 Trie for Numbers (Binary Trie)

A bitwise trie stores numbers in binary representation. It's useful for XOR queries, maximum XOR problems, and IP routing.

Structure: Each node has two children (0 and 1)
Height: Number of bits (e.g., 32 for integers)
Applications: Maximum XOR, IP routing, prefix matching

# Bitwise Trie (Binary Trie)
class BitwiseTrieNode:
    def __init__(self):
        self.children = [None, None]  # 0 and 1

class BitwiseTrie:
    def __init__(self, bits=32):
        self.root = BitwiseTrieNode()
        self.bits = bits
    
    def insert(self, num):
        node = self.root
        for i in range(self.bits - 1, -1, -1):
            bit = (num >> i) & 1
            if node.children[bit] is None:
                node.children[bit] = BitwiseTrieNode()
            node = node.children[bit]
    
    def search(self, num):
        node = self.root
        for i in range(self.bits - 1, -1, -1):
            bit = (num >> i) & 1
            if node.children[bit] is None:
                return False
            node = node.children[bit]
        return True
    
    def max_xor(self, num):
        # Find maximum XOR of num with any number in the trie
        node = self.root
        result = 0
        for i in range(self.bits - 1, -1, -1):
            bit = (num >> i) & 1
            # Want to go to opposite bit for maximum XOR
            if node.children[1 - bit] is not None:
                result |= (1 << i)
                node = node.children[1 - bit]
            else:
                node = node.children[bit]
        return result

# Example: Find Maximum XOR of two numbers in an array
def max_xor(nums):
    trie = BitwiseTrie()
    for num in nums:
        trie.insert(num)
    
    max_xor_val = 0
    for num in nums:
        max_xor_val = max(max_xor_val, trie.max_xor(num))
    
    return max_xor_val

# Example
nums = [3, 10, 5, 25, 2, 8]
print(max_xor(nums))  # 28 (25 ^ 5 = 28)

⏱️ Time & Space Complexities

Operation	Time (Trie)	Time (TST)	Space
Insert	O(L)	O(L) avg, O(L log n) worst	O(L) new nodes
Search	O(L)	O(L) avg, O(L log n) worst	O(1)
Prefix Search	O(P + K)	O(P + K) avg	O(K)
Delete	O(L)	O(L) avg	O(1)
Autocomplete	O(P + K)	O(P + K)	O(K)
Build	O(N × L)	O(N × L)	O(N × L)

L = length of word, P = prefix length, K = number of results, N = number of words

🌍 Real-World Applications

Autocomplete: Search engines, text editors, IDEs
Spell Checking: Dictionary lookup and correction suggestions
IP Routing: Longest prefix matching in routers
Dictionary Implementation: Word games (Scrabble, crossword)
Bioinformatics: DNA sequence matching
Natural Language Processing: Lexicon storage, morphological analysis
Information Retrieval: Inverted indices with prefix search
Command Line: Tab completion in shells
Data Compression: LZ78 uses tries

🧠 Advanced Trie Concepts

Persistent Trie: Versioned trie for undo/redo
Concurrent Trie: Thread-safe trie implementations
Huffman Tries: Used in Huffman coding
B-Trie: Disk-based trie for external memory
Double-Array Trie: Space-efficient array-based implementation
Burrows-Wheeler Transform: Uses suffix arrays for compression
FM-Index: Full-text index using suffix arrays and BWT

📝 Interview Patterns & Problems

🎯 Key Interview Questions

Classic: "Implement a Trie (Insert, Search, Startswith)"
Autocomplete: "Design an autocomplete system"
Word Search: "Find all words in a word search board"
Longest Word: "Find the longest word that can be built"
Word Break: "Break a string into dictionary words"
Maximum XOR: "Find maximum XOR of two numbers"
Prefix Search: "Find all words with a given prefix"
Add/Find Word: "Design Add and Search Words Data Structure"

# Interview Problem: Design Add and Search Words
class WordDictionary:
    def __init__(self):
        self.root = TrieNode()
    
    def add_word(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
    
    def search(self, word):
        def dfs(node, idx):
            if idx == len(word):
                return node.is_end
            
            char = word[idx]
            if char == '.':
                # Wildcard: try all children
                for child in node.children.values():
                    if dfs(child, idx + 1):
                        return True
                return False
            else:
                if char not in node.children:
                    return False
                return dfs(node.children[char], idx + 1)
        
        return dfs(self.root, 0)

# Interview Problem: Maximum XOR
def find_max_xor(nums):
    trie = BitwiseTrie()
    for num in nums:
        trie.insert(num)
    
    max_xor = 0
    for num in nums:
        max_xor = max(max_xor, trie.max_xor(num))
    return max_xor

# Interview Problem: Longest Word in Dictionary
def longest_word(words):
    trie = Trie()
    words.sort()
    
    for word in words:
        trie.insert(word)
    
    result = ""
    for word in words:
        # Check if all prefixes exist
        node = trie.root
        valid = True
        for i in range(len(word)):
            if word[i] not in node.children:
                valid = False
                break
            node = node.children[word[i]]
            if not node.is_end and i != len(word) - 1:
                valid = False
                break
        
        if valid and len(word) > len(result):
            result = word
    
    return result