Loading…

Module M18 · DSA Curriculum

Tries

Prefix tree — O(L) per operation regardless of how many words you've inserted. The structure behind autocomplete, spell-check, and word-search-II.

intermediatePractice Full theoryPrereq:Trees & BST

Start practice Read the theory See all problems

What you'll learn

Describe a trie node and how prefixes are shared across words
Implement insert, search, and startsWith in O(L)
Choose between an int[26] children array and a hash-map of children
Support wildcard '.' search with DFS over children
Combine a trie with grid DFS to prune Word Search II
Compare a trie to a hash set and know when each wins

When to reach for this

Signals (use it)

"Prefix" appears: startsWith, autocomplete, longest common prefix
Many words sharing prefixes, repeated prefix queries
Wildcard / pattern matching over a dictionary
Word Search II (many words against one board)
Spell-check, dictionary, or word-break style problems

Anti-signals (don't)

Only whole-word membership, no prefixes → a hash set is simpler and lighter
A handful of words queried once → trie overhead isn't worth it
Numeric ranges, not string prefixes → different structure

Theory & deep dive

A trie (pronounced 'try', from retrieval) is a tree where each edge is a character and each root-to-node path spells a prefix. Words sharing a prefix share the same path, so the structure naturally clusters by prefix — which is exactly why it powers autocomplete, spell-checkers, IP routing, and dictionary problems.

The headline property: insert, search, and prefix-check are all O(L) where L is the length of the word — completely independent of how many words are already stored. A hash set can tell you if a whole word exists in O(L) too, but it can't answer 'does any word start with this prefix?' efficiently. That prefix query is the trie's superpower.

This module covers the node structure, the insert/search/startsWith operations, the two ways to store children (fixed array vs hash map), wildcard search, and the trie + DFS combo that makes Word Search II tractable.

The big idea in plain words

A trie is like the thumb-tabs on a dictionary. Words that start the same - 'car', 'card', 'cat' - share the same path until the point where they differ, so asking 'is there any word that starts with car?' is just following the path c then a then r and seeing whether it exists.

Example: store 'cat', 'car', and 'card'. They all share the 'ca' branch; then it splits into 't' (giving cat) and 'r' (giving car), and from 'r' it continues to 'd' (giving card). Looking up or prefix-matching any word costs only as much as the word's length, no matter how many thousands of words you've stored.

What a trie is

Each node represents a prefix; its children are the possible next characters; a boolean flag marks nodes that complete a word.

Term	Meaning
Node	One prefix; holds child links + `isEnd` flag
Edge	A single character leading to a child
isEnd / isWord	True if the path to here spells a complete inserted word
Root	Empty prefix; entry point for all words

Inserting 'car', 'card', 'cat' shares the 'ca' path: 'c'→'a' splits into 't' and 'r', and 'r'→'d'. Shared prefixes are stored once, which is both the space win and the reason prefix queries are fast.

Tip

The isEnd flag is essential: without it you can't tell 'car' (an inserted word) from 'ca' (just a prefix on the way to 'car'/'cat'). search() must check isEnd; startsWith() does not.

Two ways to store children

Children storage	Pros	Cons	Use when
Fixed array `[26]` (or 128)	O(1) child access, cache-friendly	wastes space for sparse nodes	lowercase a–z, dense
Hash map char→node	only allocates used children	slight overhead per access	large/unknown alphabet, sparse

For the standard 'lowercase English letters' constraint, the int[26] / TrieNode[26] array is the conventional choice and what interviewers usually expect. Switch to a hash map when the alphabet is large or Unicode.

Insert, search, startsWith

All three walk the trie character by character from the root. Insert creates missing child nodes along the way and sets isEnd at the last character. Search walks and then checks isEnd. startsWith walks and just confirms the path exists. Every operation is O(L) in the word length.

Java· Trie (int[26] children array)

class Trie {
    Trie[] kids = new Trie[26];
    boolean isEnd;
    void insert(String w) {
        Trie node = this;
        for (char c : w.toCharArray()) {
            int i = c - 'a';
            if (node.kids[i] == null) node.kids[i] = new Trie();
            node = node.kids[i];
        }
        node.isEnd = true;
    }
    boolean search(String w) { Trie n = walk(w); return n != null && n.isEnd; }
    boolean startsWith(String p) { return walk(p) != null; }
    private Trie walk(String s) {
        Trie node = this;
        for (char c : s.toCharArray()) {
            node = node.kids[c - 'a'];
            if (node == null) return null;
        }
        return node;
    }
}

Wildcard search

'Add and Search Word' allows a '.' that matches any single character. The walk becomes a small DFS: on a normal character, descend that one child; on a '.', recurse into all present children. Everything else is the same O(L) walk, now branching only where wildcards appear.

Python· Wildcard '.' search (DFS)

def search_wildcard(node, word, i=0):
    if i == len(word):
        return '$' in node
    c = word[i]
    if c == '.':
        return any(search_wildcard(child, word, i + 1)
                   for k, child in node.items() if k != '$')
    return c in node and search_wildcard(node[c], word, i + 1)

Trie + DFS: Word Search II

Searching a grid for each of many words independently is O(words × board). Instead, build a trie of all the words, then DFS the board once, walking the trie in lockstep with the path on the board. The trie lets you prune the instant the current path isn't a prefix of any word — you stop exploring dead ends immediately. This combination is the canonical reason tries appear in hard interviews.

Note

In Word Search II, mark a trie word as found (or remove its end flag) after collecting it to avoid duplicates, and unmark grid cells on backtrack — it's backtracking and trie traversal at the same time.

How to talk about this in the interview

“Justify the trie over a hash set by the prefix requirement: "A hash set answers whole-word membership in O(L), but this needs prefix queries — 'does any word start with this?' — which a trie does in O(L) while a set can't." State the children-storage choice and why: "Lowercase only, so I'll use a 26-slot array for O(1) child access." For Word Search II, lead with the pruning win: "I'll put all words in a trie and DFS the board once, pruning the moment the current path isn't a prefix of any word." Give O(L) per operation and O(total characters) space.”

Common mistakes

–Forgetting the isEnd flag, so prefixes are mistaken for complete words
–Using a trie when a hash set suffices (no prefix queries needed) — wasted complexity
–Not unmarking grid cells on backtrack in Word Search II
–Collecting duplicate words in Word Search II (unmark/remove found words)
–Sizing the children array wrong for the alphabet (uppercase, digits, Unicode)
–Quoting O(1) for operations — it's O(L), the word length

Complexity summary

Insert, search, and startsWith are O(L) time in the word length, independent of the number of stored words. Space is O(total characters across all words × alphabet) worst case. Word Search II is roughly O(cells × 4^maxWordLen) but trie pruning cuts this dramatically in practice.

Practice problems

4 total

Implement Trie (Prefix Tree)

AmazonGoogleMicrosoft

mediumExplained

Design Add and Search Words Data Structure

M17 · Math & Number Theory

GCD, primes, and modular arithmetic.

Curriculum complete

Back to DSA hub

Pick any module to revise

Module M18 · DSA Curriculum

Tries

Prefix tree — O(L) per operation regardless of how many words you've inserted. The structure behind autocomplete, spell-check, and word-search-II.

intermediatePractice Full theoryPrereq:Trees & BST

Start practice Read the theory See all problems

What you'll learn

Describe a trie node and how prefixes are shared across words
Implement insert, search, and startsWith in O(L)
Choose between an int[26] children array and a hash-map of children
Support wildcard '.' search with DFS over children
Combine a trie with grid DFS to prune Word Search II
Compare a trie to a hash set and know when each wins

When to reach for this

Signals (use it)

"Prefix" appears: startsWith, autocomplete, longest common prefix
Many words sharing prefixes, repeated prefix queries
Wildcard / pattern matching over a dictionary
Word Search II (many words against one board)
Spell-check, dictionary, or word-break style problems

Anti-signals (don't)

Only whole-word membership, no prefixes → a hash set is simpler and lighter
A handful of words queried once → trie overhead isn't worth it
Numeric ranges, not string prefixes → different structure

Theory & deep dive

The big idea in plain words

What a trie is

Each node represents a prefix; its children are the possible next characters; a boolean flag marks nodes that complete a word.

Term	Meaning
Node	One prefix; holds child links + `isEnd` flag
Edge	A single character leading to a child
isEnd / isWord	True if the path to here spells a complete inserted word
Root	Empty prefix; entry point for all words

Tip

The isEnd flag is essential: without it you can't tell 'car' (an inserted word) from 'ca' (just a prefix on the way to 'car'/'cat'). search() must check isEnd; startsWith() does not.

Two ways to store children

Children storage	Pros	Cons	Use when
Fixed array `[26]` (or 128)	O(1) child access, cache-friendly	wastes space for sparse nodes	lowercase a–z, dense
Hash map char→node	only allocates used children	slight overhead per access	large/unknown alphabet, sparse

Insert, search, startsWith

Java· Trie (int[26] children array)

class Trie {
    Trie[] kids = new Trie[26];
    boolean isEnd;
    void insert(String w) {
        Trie node = this;
        for (char c : w.toCharArray()) {
            int i = c - 'a';
            if (node.kids[i] == null) node.kids[i] = new Trie();
            node = node.kids[i];
        }
        node.isEnd = true;
    }
    boolean search(String w) { Trie n = walk(w); return n != null && n.isEnd; }
    boolean startsWith(String p) { return walk(p) != null; }
    private Trie walk(String s) {
        Trie node = this;
        for (char c : s.toCharArray()) {
            node = node.kids[c - 'a'];
            if (node == null) return null;
        }
        return node;
    }
}

Wildcard search

Python· Wildcard '.' search (DFS)

def search_wildcard(node, word, i=0):
    if i == len(word):
        return '$' in node
    c = word[i]
    if c == '.':
        return any(search_wildcard(child, word, i + 1)
                   for k, child in node.items() if k != '$')
    return c in node and search_wildcard(node[c], word, i + 1)

Trie + DFS: Word Search II

Note

How to talk about this in the interview

Common mistakes

–Forgetting the isEnd flag, so prefixes are mistaken for complete words
–Using a trie when a hash set suffices (no prefix queries needed) — wasted complexity
–Not unmarking grid cells on backtrack in Word Search II
–Collecting duplicate words in Word Search II (unmark/remove found words)
–Sizing the children array wrong for the alphabet (uppercase, digits, Unicode)
–Quoting O(1) for operations — it's O(L), the word length