Tries

What is a trie?

A trie (prefix tree) is a tree where each node represents one character of a string. A path from the root to a node marked is_end = True spells a complete word. Every word sharing a prefix shares that prefix's nodes - "cat" and "car" both pass through the c and a nodes before diverging at the third character.

class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_end = False  # True if a word ends here

The root node is empty. Inserting "cat" means creating or following nodes for c → a → t, then marking t.is_end = True. A subsequent insert of "car" reuses the existing c and a nodes and only creates a new r node.

The core trade-off: O(m) insert, search, and prefix-check where m is the word length. A hash set also gives O(m) exact search but cannot answer "does any word start with prefix X" without scanning all words. The trie makes prefix queries O(m) with no extra overhead.

Core operations

Key patterns

Insert and search

The same traversal pattern drives both: for each character, get or create node.children[char]. After the loop, is_end marks whether the path spells a complete word. The only behavioral difference is that insert creates missing nodes while search returns False on the first missing character.

When to use - you need exact-word storage plus the ability to ask whether any word starts with a given prefix. A hash set gives you exact lookup but cannot answer the prefix question without scanning every word at O(n*m). The trie collapses both into a single character-by-character walk.

How it works - each node holds a children map from character to the next node and an is_end flag. To insert, walk the word one character at a time, creating a node wherever the edge is missing, then set is_end = True on the final node so the path is marked as a complete word. To search, walk the same path but return False the moment a character has no edge. The only reason search and starts_with differ is the final check: search returns node.is_end because the word must actually terminate there, while starts_with returns True as long as the path exists. Every operation touches one node per character, so each is O(L) for a word of length L.

DFS from a prefix node (autocomplete)

Navigate to the prefix node, then recursively collect all complete words reachable from it. Pass a mutable path list that accumulates characters; append to results when is_end is True.

When to use - the problem asks for every word that begins with a given prefix: autocomplete, search suggestions, or "list all completions". A hash set would force you to scan all n words and test each one. The trie lets you jump straight to the prefix node and walk only the words that actually share it.

How it works - first walk the prefix character by character to reach the node where every word with that prefix branches off. From there, run a DFS that descends into each child, appending the edge character to a running path and recording the word whenever it lands on a node with is_end = True. Because the prefix navigation already pruned everything else, the work is O(m + k): m characters to reach the prefix node, plus k characters across all the words you collect. The descent visits only nodes that belong to a matching word, so nothing outside the prefix is ever touched.

Canonical examples

Implement Trie

Build all three operations. The key insight: insert and search share the same character-by-character traversal; the only difference is whether missing nodes are created (insert) or cause early return (search and starts_with).

Word search II (trie + backtracking)

Given a board and a list of words, find all words present in the board. The naive approach runs backtracking once per word: O(W * 4^L). With a trie, build a trie of all words, then run one backtracking pass over the board - at each cell, follow the trie as you explore, pruning branches that no word uses.

When to reach for a trie

• The problem asks whether any word in a dictionary starts with a given prefix - a hash set cannot do this efficiently.
• You need autocomplete - given a prefix, return all completions.
• The problem involves searching for multiple words simultaneously in a grid (word search II) - a trie lets you prune paths no word uses.
• You need to find the longest common prefix of a set of strings.
• The problem involves replacing or matching words by prefix in a sentence.

Practice problems

• Implement Trie (Prefix Tree) - Build insert, search, and startsWith.
• Search Suggestions System - Trie + DFS for autocomplete on each keystroke.
• Replace Words - Trie lookup to replace words with their shortest dictionary root.
• Word Search II - Trie + backtracking; prune board paths using the trie.
• Design Add and Search Words Data Structure - Trie with . wildcard matching via DFS.