🌲 Trie Algorithms

Master prefix trees (tries) for efficient string search, autocomplete, and prefix matching operations.

Overview

ℹ️

What is a Trie?

A trie (prefix tree) is a tree data structure where each node represents a character. Words are stored by traversing from root to leaf, sharing common prefixes. This enables O(L) search and efficient prefix operations that hash tables can't do.

Key Trie Algorithms

Trie Insert & Search

Insert words into trie and search for exact matches

Time: O(L)Space: O(N*L)

Prefix Search & Autocomplete

Find all words with given prefix

Time: O(L + M)Space: O(N*L)

Word Break (Trie)

Check if string can be segmented into dictionary words

Time: O(n²)Space: O(n + N*L)

Maximum XOR Pair

Find two numbers with maximum XOR using trie

Time: O(n*32)Space: O(n*32)

Interactive Visualizer

Trie Visualization

🌲

Trie Insert & Search Trie Visualizer

Watch how words are inserted, searched, and how common prefixes share nodes in the trie.

Deep Dive: Trie Insert & Search

Time Complexity

Time: O(L)

Space Complexity

Space: O(N*L)

Best For

Prefix Operations

💡

Trie Strategy

Insert: traverse character by character, creating nodes as needed. Mark the final node as end of word. Search: traverse characters, return is_end at final node.

python

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
    
    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

1

Define Node

Each node has children (dictionary/hash map) and an end-of-word flag.

2

Insert

Traverse character by character, creating missing nodes. Mark last node as end.

3

Search

Traverse characters. Return false if any character missing. Return is_end at final node.

4

Prefix Query

Navigate to prefix node, then collect all words in its subtree via DFS.

Real-World Applications

Autocomplete

Search engines, IDE code completion, text prediction

Spell Checkers

Dictionary lookup with suggestions for misspelled words

IP Routing

Longest prefix matching in network routers

Search Engines

Inverted index, prefix-based query suggestions

Phone Directory

Contact search by name prefix

Bioinformatics

Gene sequence pattern matching

Interview Questions

When would you use trie over hash table?

Trie excels when: 1) Prefix search is needed (autocomplete), 2) Words share common prefixes (memory efficient), 3) Lexicographic ordering is needed, 4) You need longest prefix matching (routing). Hash table can't do prefix search efficiently.

What are the memory tradeoffs of trie?

Trie can use more memory than hash table for non-overlapping words (each node is an object). But for words with shared prefixes (like 'test', 'testing', 'tested'), trie is more memory efficient. Compressed trie (radix tree) reduces memory.

How would you implement autocomplete with trie?

Insert all dictionary words. For a prefix, navigate to prefix node, then perform DFS to collect all words under that node. Sort by frequency/rank. Can optimize with top-k suggestions per node.

Knowledge Check

1. What is the time complexity of trie search?

2. What does each node in a trie store?

3. What is the main advantage of trie over hash set?

4. Space complexity of a trie with N words of avg length L?

5. Which problem is best solved with trie?