λDSA Learning Hubpart of DSA Atlas

Tries (Prefix Trees)

Intermediate~3h · 7 lessons10 practice problems

One character per edge, shared prefixes shared once: O(L) insert/search independent of dictionary size, prefix search, autocomplete, and XOR tries.

0 of 7 lessons checked off

Introduction

What it is

  • A trie (from reTRIEval, pronounced 'try') stores strings as paths: each edge is one character, each node one prefix. Words sharing a prefix share that path — 'car', 'cat' and 'care' share c → a.
  • A boolean is_word flag marks nodes that end complete words, distinguishing the stored word 'car' from the mere prefix 'ca'.

Why it matters

  • Its costs depend on the WORD's length L, not the dictionary's size n: insert, search, and prefix-check are all O(L) whether the trie holds ten words or ten million.
  • It answers the query hash maps can't: 'does anything start with pre-…?' A hash of complete words knows nothing about prefixes; the trie IS the prefix structure.

How it works

  • Each node keeps a children map (char → node) plus is_word. Insert walks the word's characters, creating missing nodes; search walks and checks is_word; prefix-search walks and doesn't.
  • Autocomplete = walk to the prefix node, then DFS its subtree collecting flagged words.

Where it's used

  • Search-box suggestions, phone contact search, spell checkers, IP routing (longest-prefix match on bit tries), and T9 keyboards are all tries at work.

In interviews

  • Implement Trie (LC 208), Design Add and Search Words (with '.' wildcards → DFS branching), Word Search II (trie + board backtracking), and Maximum XOR of Two Numbers (bitwise trie).
Analogy: A city of words: from the central square (root), each street sign adds a letter. Every address you pass is a prefix; buildings with a flag on the roof (is_word) are real words. All 'car…' addresses share the same first two streets — that sharing is the entire economy of the structure.

Interactive diagram

The walk reuses c → a → r, creates only one new node ('e'), and flags it as a word end.

rtac•
Trie holding "car", "cat"

Each edge stores one character; shared prefixes share nodes. Filled dots mark ends of complete words. Now insert "care" character by character.

Lessons in this topic

Check off lessons as you go — your progress is saved in this browser.

  1. Trie node structure

    children map + is_word; why edges, not nodes, hold characters.

    15 min
  2. Insert, character by character

    Walk and create; mark the final node.

    20 min
  3. Search word vs prefix search

    The same walk; only the final check differs.

    20 min
  4. Delete a word

    Unflag, then prune childless unflagged nodes bottom-up.

    20 min
  5. Autocomplete and dictionary search

    Prefix walk + subtree DFS; ranking by frequency.

    25 min
  6. Wildcard search ('.')

    Branching DFS over all children at wildcard positions.

    20 min
  7. Bitwise tries and maximum XOR

    Binary alphabet over bit positions; greedy opposite-bit walks.

    25 min

Operations

Insert a word

Walk the characters from the root, creating nodes only where the path is missing; flag the last node. Cost: the word's length, regardless of dictionary size.

rtac•
Trie holding "car", "cat"

Each edge stores one character; shared prefixes share nodes. Filled dots mark ends of complete words. Now insert "care" character by character.

class TrieNode:    __slots__ = ("children", "is_word")    def __init__(self) -> None:        self.children: dict[str, "TrieNode"] = {}        self.is_word = Falseclass Trie:    def __init__(self) -> None:        self.root = TrieNode()    def insert(self, word: str) -> None:        """O(L) time, O(L) new nodes worst case."""        node = self.root        for ch in word:            if ch not in node.children:                node.children[ch] = TrieNode()   # grow only when missing            node = node.children[ch]        node.is_word = True                       # mark the complete word
Time: O(L), L = word lengthSpace: O(L) new nodes worst case (zero if the word was a stored prefix)

Edge cases

  • Inserting a word twice is a no-op after the first flag.
  • Inserting a prefix of an existing word ('car' after 'care') creates nothing — it only flags.
  • Empty string: flags the root; decide whether your API allows it.

Common mistakes

  • Forgetting is_word = True — the walk succeeds but the word is invisible to search.
  • Storing characters IN nodes instead of on edges (the children keys) — it double-counts and confuses deletion.

Search word and prefix search

Both walk the same path. search() demands the final node be flagged; starts_with() only demands the path exists — the one-line difference that defines the trie.

Search word and prefix search
class Trie(TrieBase := object):  # continuing the class above    def _walk(self, s: str) -> "TrieNode | None":        node = self.root        for ch in s:            node = node.children.get(ch)            if node is None:                return None                # path breaks: nothing starts with s        return node    def search(self, word: str) -> bool:        """Is word a COMPLETE stored word? O(L)."""        node = self._walk(word)        return node is not None and node.is_word    def starts_with(self, prefix: str) -> bool:        """Does ANY stored word begin with prefix? O(L)."""        return self._walk(prefix) is not None
Time: O(L) both — independent of how many words are storedSpace: O(1)

Edge cases

  • search('ca') on a trie holding 'car': path exists, flag doesn't → False, while starts_with('ca') → True. THE distinction to articulate.
  • Prefix longer than any word: walk breaks → both False.
  • Case sensitivity: normalise on insert AND search, consistently.

Common mistakes

  • search returning true on any complete path (missing the is_word check).
  • Catching KeyError instead of using .get — works, but hides logic and is slower.

Autocomplete (all words with a prefix)

Walk to the prefix node — O(P) — then DFS its subtree, rebuilding words as you descend and collecting flagged nodes.

Autocomplete (all words with a prefix)
    def words_with_prefix(self, prefix: str, limit: int = 10) -> list[str]:        """Up to 'limit' completions of prefix. O(P + collected output)."""        node = self._walk(prefix)        if node is None:            return []        results: list[str] = []        def dfs(current: "TrieNode", path: list[str]) -> None:            if len(results) >= limit:          # stop early — UX never needs all                return            if current.is_word:                results.append(prefix + "".join(path))            for ch in sorted(current.children):   # alphabetical suggestions                path.append(ch)                dfs(current.children[ch], path)                path.pop()                      # backtrack        dfs(node, [])        return results
Time: O(P) to reach the prefix + O(output) to collectSpace: O(depth) recursion

Edge cases

  • Prefix itself is a word: it appears first (root of the DFS is flagged).
  • Nonexistent prefix: empty list, no exception.
  • Real autocompletes rank by frequency — store counts on word nodes and pop from a heap (say it as the follow-up).

Common mistakes

  • Collecting the entire subtree when a limit was given — autocomplete latency dies on dense prefixes.
  • Forgetting path.pop() — the backtracking bug that corrupts every later suggestion.

Delete a word

Unflag the word node; then, walking back up, prune nodes that are now childless and unflagged — never touch shared prefixes.

Delete a word
    def delete(self, word: str) -> bool:        """Remove word if present, pruning dead branches. O(L)."""        def helper(node: "TrieNode", depth: int) -> bool:            """Returns True if this node should be deleted by its parent."""            if depth == len(word):                if not node.is_word:                    return False               # word wasn't stored                node.is_word = False                return not node.children       # prune only if now dead            ch = word[depth]            child = node.children.get(ch)            if child is None or not helper(child, depth + 1):                return False            del node.children[ch]              # child said "delete me"            return not node.children and not node.is_word        return bool(helper(self.root, 0)) or self.search(word) is False
Time: O(L)Space: O(L) recursion

Edge cases

  • Deleting 'car' when 'care' exists: only the flag flips — the path is shared and must survive.
  • Deleting 'care' when 'car' exists: prune 'e' only; stop at the flagged 'r'.
  • Deleting an absent word must change nothing.

Common mistakes

  • Deleting every node on the path unconditionally, destroying sibling words.
  • Pruning a node that is still flagged as another word's end.

Bitwise trie: maximum XOR pair

Insert numbers as 32-bit paths. For each number, greedily walk toward the OPPOSITE bit at every level — that path maximises the XOR.

Bitwise trie: maximum XOR pair
def find_maximum_xor(nums: list[int]) -> int:    """Max of a ^ b over all pairs. O(32n) time and space."""    BITS = 32    root: dict[int, dict] = {}    for x in nums:                       # build: one path per number        node = root        for i in range(BITS - 1, -1, -1):            bit = (x >> i) & 1            node = node.setdefault(bit, {})    best = 0    for x in nums:                       # query: chase opposite bits        node = root        acc = 0        for i in range(BITS - 1, -1, -1):            bit = (x >> i) & 1            want = 1 - bit               # opposite bit doubles this position
Time: O(32n) build + O(32n) query = O(n)Space: O(32n)

Edge cases

  • Single element: best XOR is 0 (x ^ x).
  • Fix BITS to the value range's width; too few bits silently truncates.
  • Most-significant bit FIRST — greedy is only correct top-down.

Common mistakes

  • Iterating bits low-to-high — greedy on low bits sacrifices high bits and is wrong.
  • Trying all pairs (O(n²)) when the trie gives O(n) — the entire point of the question.

Complexity analysis

OperationBestAverageWorstSpace
insert(word)O(L)O(L)O(L)O(L) new nodes
search(word) / starts_withO(L)O(L)O(L)O(1)
delete(word)O(L)O(L)O(L)O(L) stack
autocomplete(prefix)O(P)O(P + output)O(P + subtree)O(depth)
hash-set search (contrast)O(L)O(L)O(nL)—

L = word length, P = prefix length, n = words stored. The headline: nothing here depends on n — and the hash set simply cannot do the prefix rows.

Python implementation

Production-quality code with type hints, validation, and docstrings.

Wildcard dictionary: add words, search with '.' (LC 211)
class TrieNode:    __slots__ = ("children", "is_word")    def __init__(self) -> None:        self.children: dict[str, "TrieNode"] = {}        self.is_word = Falseclass WordDictionary:    """add_word O(L); search supports '.' matching any character."""    def __init__(self) -> None:        self.root = TrieNode()    def add_word(self, word: str) -> None:        node = self.root        for ch in word:            node = node.children.setdefault(ch, TrieNode())

What interviewers expect you to know

What interviewers expect you to know

  • Costs are O(word length), independent of dictionary size — say this unprompted; it's the trie's thesis.
  • search vs starts_with differ ONLY in the final is_word check.
  • Space is the trade-off: up to 26 pointers per node; children-as-dict keeps it proportional to real edges.
  • The word-end flag is load-bearing: without it, prefixes and words are indistinguishable.

Pattern triggers

  • 'prefix', 'autocomplete', 'starts with', 'dictionary of words' → trie.
  • 'maximum XOR' → bitwise trie with greedy opposite-bit walks.
  • 'search many words in a grid' → trie of the words + one board DFS (Word Search II).
  • Wildcards in patterns → DFS branching at '.' nodes.

Classic follow-ups

  • "Trie vs hash set?" — set: exact membership, less memory. Trie: prefix queries, ordered enumeration, wildcard matching, shared-prefix compression.
  • "Memory too high?" — arrays of 26 vs dicts, radix/Patricia compression (merge single-child chains), or DAWG for shared suffixes. Naming them is full credit.
  • "How would you rank autocomplete?" — store frequency at word nodes; best-first (heap) over the subtree.

Common mistakes

Missing is_word check in search

A successful walk proves the PREFIX exists, not the word. search('ca') must be False when only 'car' and 'care' are stored.

Destructive deletes

Deleting 'car' by removing its whole path also kills 'care'. Unflag first; prune only childless, unflagged nodes bottom-up.

Rebuilding strings during DFS

prefix + ch at every level allocates O(L) per node — collect into a shared list with append/pop and join at word nodes.

Wrong bit order in XOR tries

Greedy opposite-bit selection is only valid most-significant-bit first. Low-bit-first tries produce confidently wrong answers.

Assuming a 26-letter alphabet

children = [None] * 26 crashes on 'É' or digits. State the assumption or use a dict.

Practice problems

Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.

Easy (2)

Medium (6)

Implement Trie
MediumPrefix tree construction and traversal~25 min

Commonly associated with: Amazon, Google, Microsoft, Bloomberg

O(L) per operation, where L is the word/prefix length time · O(total characters inserted) space

Hard (2)

Topic quiz

5 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.

  1. Code output1. After insert('car'), insert('care'): what do search('car') and search('ca') return?
  2. Complexity2. A trie holds 1,000,000 words. Searching a 6-letter word costs…
  3. Scenario3. Search-as-you-type must list completions of 'th' from a large dictionary. Why is a hash set of words a poor fit?
  4. Concept4. Deleting 'care' from a trie that also holds 'car': which nodes go?
  5. Concept5. In the maximum-XOR bitwise trie, at each bit level you try to walk toward…
0 of 5 answered

Frequently asked questions

Dict children or a 26-slot array — which should I write in interviews?

Dict (or setdefault) — it's shorter, alphabet-agnostic, and allocation-proportional to real edges. Mention the array as the cache-friendly option when the alphabet is fixed and density is high.

How much memory does a trie really cost?

Worst case O(total characters) nodes, each with map overhead — heavier than a hash set of the same words. Shared prefixes claw memory back; compressed tries (radix/Patricia) merge single-child chains when it matters.

Where does the word 'trie' come from?

From reTRIEval (Edward Fredkin, 1960). Commonly pronounced 'try' to distinguish it from 'tree' — either is understood in interviews.

Summary & cheat sheet

Key takeaways

  • Trie costs scale with word length, never dictionary size.
  • is_word flags separate stored words from mere prefixes — search vs starts_with is one boolean.
  • Autocomplete = prefix walk + subtree DFS (with backtracking and a limit).
  • Delete = unflag, then prune only dead branches.
  • Binary alphabet + MSB-first greedy = the XOR-maximisation trie.

Formulas & cheat sheet

  • insert/search/prefix: O(L); autocomplete: O(P + output)
  • Nodes ≤ total characters inserted + 1
  • XOR trie: 32 levels; answer bit i = 1 iff opposite branch existed at level i

Interview checklist

  • I can implement insert/search/starts_with in under five minutes.
  • I can explain why search('ca') is False after inserting 'car'.
  • I can write autocomplete with proper backtracking.
  • I can describe safe deletion and the XOR-trie greedy.