Tries (Prefix Trees) — Complete Interview Guide for FAANG Engineers

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) with shared prefix storage. Google, Amazon, and Meta use tries in autocomplete, IP routing, and spell-checking — making this a high-frequency interview topic.

Core Trie Node Structure

class TrieNode:
    def __init__(self):
        self.children = {}   # dict maps char to TrieNode; or [None]*26 for lowercase
        self.is_end = False  # True only when a complete word ends here

The two data members are all you need. Every trie problem is a variation on these two.

The 5 Core Trie Patterns

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

def insert(root, 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(root, word):
    node = root
    for c in word:
        if c not in node.children:
            return False
        node = node.children[c]
    return node.is_end   # must check is_end for exact match
 
def starts_with(root, prefix):
    node = root
    for c in prefix:
        if c not in node.children:
            return False
        node = node.children[c]
    return True   # no is_end check needed for prefix

Pattern 2 — Trie + DFS for Word Search II

Build a trie from the word list. DFS on the grid, traversing the trie simultaneously — prune entire subtrees when no trie path exists. Set node.word = word at the end node instead of is_end = True to recover the matched word without backtracking.

Pattern 3 — Trie with Count / Delete

Track count of words with this prefix. Increment on insert, decrement on delete. When count reaches 0, unlink the node.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.count = 0    # words passing through this node
        self.is_end = False

Pattern 4 — XOR Binary Trie (Max XOR)

Build a binary trie bit by bit from MSB to LSB. For each number, greedily take the opposite bit to maximize XOR.

def insert_bit(root, 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]
 
def max_xor_query(root, x):
    node = root
    xor = 0
    for bit in range(31, -1, -1):
        b = (x >> bit) & 1
        want = 1 - b   # prefer opposite bit to maximize XOR
        if want in node.children:
            xor = (xor << 1) | 1
            node = node.children[want]
        else:
            xor = xor << 1
            node = node.children[b]
    return xor

Pattern 5 — Autocomplete / Ranked Suggestions

Store sorted word lists at each trie node, or DFS from the prefix node to collect all words (then sort). For LC 1268 Search Suggestions, binary search on a sorted array is simpler.

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)
Build trie for n words of avg len L	O(n*L)	O(nL26) array or O(n*L) dict

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

Decision Guide

Need prefix search?           → Trie (vs HashSet which cannot prefix-query)
Multiple words in grid?       → Trie + Grid DFS (Word Search II, pruning)
Autocomplete with ranking?    → Trie + sorted lists at each node
Max/Min XOR of two numbers?   → Binary Trie (bit by bit, MSB first)
Suffix matching?              → Reversed Trie
Count words with prefix?      → Trie with count field at each node
Prefix + suffix search?       → Concatenate "suf#pref" as trie key

Problem Index

#	Problem	Pattern	Difficulty
01	Implement Trie	Basic insert/search/prefix	Medium
02	Design Add and Search Words	Trie + wildcard DFS	Medium
03	Word Search II	Trie + Grid DFS pruning	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 key	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 field	Easy
18	Sum of Prefix Scores	Trie prefix count	Hard
19	Longest Common Prefix via Trie	Trie digit keys	Medium
20	Tries Master Recap	Cheatsheet	—

Key Takeaways

A trie node has exactly two components: a children map/array and an is_end boolean — everything else is optional metadata.
search requires both a valid path and is_end = True; startsWith only requires a valid path.
The is_end check is what distinguishes an exact word match from a prefix match — the most common trie bug is missing it.
Word Search II uses a trie to prune DFS on a grid — if the current path prefix does not exist in the trie, no word in the list can match.
Binary trie (bit by bit from MSB) enables greedy maximum XOR in O(32) per query after O(32n) build.
Trie space complexity is O(n * L * ALPHABET_SIZE) for array children — use a dictionary for sparse alphabets.
Every trie problem in interviews reduces to one of the five core patterns: basic, grid DFS, count/delete, binary XOR, or autocomplete.

What is a Trie?#

Core Trie Node Structure#

The 5 Core Trie Patterns#

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

Pattern 2 — Trie + DFS for Word Search II#

Pattern 3 — Trie with Count / Delete#

Pattern 4 — XOR Binary Trie (Max XOR)#

Pattern 5 — Autocomplete / Ranked Suggestions#

Complexity Reference#

5-Language Trie Node#

C — Array-based#

C++ — unordered_map#

Java — Array children#

JavaScript — Object children#

Decision Guide#

Problem Index#

Key Takeaways#

Related reading