Tries (Prefix Trees) — Complete Guide

What is a Trie?

A Trie (prefix tree) is a tree where each node represents one character. Paths from root to a node spell out a string prefix. It enables O(L) insert, search, and prefix-check (L = string length).

Core Trie Node Structure

class TrieNode:
    def __init__(self):
        self.children = {}   # or [None]*26 for lowercase only
        self.is_end = False

The 5 Core Trie Patterns

Pattern 1 — Basic Trie (Insert / Search / StartsWith)

def insert(word):
    node = root
    for c in word:
        if c not in node.children:
            node.children[c] = TrieNode()
        node = node.children[c]
    node.is_end = True

def search(word):
    node = root
    for c in word:
        if c not in node.children: return False
        node = node.children[c]
    return node.is_end

def starts_with(prefix):
    node = root
    for c in prefix:
        if c not in node.children: return False
        node = node.children[c]
    return True

Pattern 2 — Trie + DFS for Word Search II

Build a trie from the word list. DFS on the grid, traversing the trie simultaneously — prune when no trie path exists.

Pattern 3 — Trie with Count / Delete

Track count of words with this prefix. Decrement on delete.

Pattern 4 — XOR Trie (Max XOR)

Build a binary trie (bit by bit, MSB first). For each number, greedily take opposite bit to maximize XOR.

# Binary trie insert (bit by bit)
def insert(num):
    node = root
    for bit in range(31, -1, -1):
        b = (num >> bit) & 1
        if b not in node.children:
            node.children[b] = TrieNode()
        node = node.children[b]

Pattern 5 — Autocomplete / Ranked Suggestions

Trie with sorted word lists at each node, or DFS from prefix node to collect all words.

Complexity Reference

Operation	Time	Space
Insert word	O(L)	O(L) per word
Search word	O(L)	O(1)
Prefix search	O(L)	O(1)
Word Search II	O(MN4^L) pruned	O(total word chars)
Max XOR pair	O(32*n)	O(32*n)

5-Language Trie Node

C — Array-based

typedef struct TrieNode {
    struct TrieNode* ch[26];
    int isEnd;
} TrieNode;
TrieNode* newNode(){
    TrieNode* n=calloc(1,sizeof(TrieNode)); n->isEnd=0; return n;
}
void insert(TrieNode* root, char* word){
    TrieNode* cur=root;
    for(;*word;word++){
        int i=*word-'a';
        if(!cur->ch[i]) cur->ch[i]=newNode();
        cur=cur->ch[i];
    }
    cur->isEnd=1;
}

C++ — unordered_map

struct TrieNode {
    unordered_map<char,TrieNode*> ch;
    bool isEnd=false;
};
class Trie {
    TrieNode* root=new TrieNode();
public:
    void insert(string w){
        auto* cur=root;
        for(char c:w){if(!cur->ch.count(c))cur->ch[c]=new TrieNode();cur=cur->ch[c];}
        cur->isEnd=true;
    }
    bool search(string w){
        auto* cur=root;
        for(char c:w){if(!cur->ch.count(c))return false;cur=cur->ch[c];}
        return cur->isEnd;
    }
};

Java — array children

class Trie {
    Trie[] ch = new Trie[26];
    boolean isEnd;
    public void insert(String w){
        Trie cur=this;
        for(char c:w.toCharArray()){
            int i=c-'a';
            if(cur.ch[i]==null) cur.ch[i]=new Trie();
            cur=cur.ch[i];
        }
        cur.isEnd=true;
    }
    public boolean search(String w){
        Trie cur=this;
        for(char c:w.toCharArray()){int i=c-'a';if(cur.ch[i]==null)return false;cur=cur.ch[i];}
        return cur.isEnd;
    }
}

JavaScript — object children

class TrieNode {
    constructor(){ this.ch={}; this.isEnd=false; }
}
class Trie {
    constructor(){ this.root=new TrieNode(); }
    insert(w){ let n=this.root; for(const c of w){if(!n.ch[c])n.ch[c]=new TrieNode();n=n.ch[c];}n.isEnd=true; }
    search(w){ let n=this.root; for(const c of w){if(!n.ch[c])return false;n=n.ch[c];}return n.isEnd; }
}

Problem Index

#	Problem	Pattern	Difficulty
01	Implement Trie	Basic Trie	Medium
02	Design Add and Search Words	Trie + wildcard DFS	Medium
03	Word Search II	Trie + Grid DFS	Hard
04	Replace Words	Trie prefix replacement	Medium
05	Map Sum Pairs	Trie with value sum	Medium
06	Maximum XOR of Two Numbers	Binary Trie	Medium
07	Longest Word in Dictionary	Trie + BFS	Medium
08	Index Pairs of a String	Trie text matching	Easy
09	Search Suggestions System	Trie + sorted lists	Medium
10	Stream of Characters	Trie reverse suffix	Hard
11	Palindrome Pairs	Trie + palindrome check	Hard
12	Concatenated Words	Trie + word break	Hard
13	Count Distinct Substrings	Suffix Trie	Medium
14	Prefix and Suffix Search	Double-end trie	Hard
15	Short Encoding of Words	Trie + suffix	Medium
16	Maximum XOR With an Element	Binary Trie + offline	Hard
17	Count Words Beginning Prefix	Trie count	Easy
18	Sum of Prefix Scores	Trie prefix count	Hard
19	Find the Length of the Longest Common Prefix	Trie digit	Medium
20	Tries Master Recap	Cheatsheet	—