Tries Explained Simply (With Real Interview Problems)

July 6, 2026

Tries Explained Simply (With Real Interview Problems)

Every time your phone suggests “birthday” after you type “birt”, a trie (or one of its descendants) is doing the work. The trie — also called a prefix tree — is the data structure interviewers reach for when they want to test whether you can go beyond hash maps, and it anchors several famous problems: autocomplete, Word Search II, and Longest Word in Dictionary.

The good news: tries are genuinely simple once you see one drawn out. In this post we’ll build the mental model, implement a trie in Python from scratch, and then solve those three classic problems with it. For the lesson version inside our structured challenge, see Day 58: Tries.

What Is a Trie?

A trie is a tree where each edge is labeled with a character, and each path from the root spells a prefix. Words that share a prefix share a path. Here’s a trie containing cat, car, card, and dog:

 1              (root)
 2              /    \
 3            c        d
 4            |        |
 5            a        o
 6           / \       |
 7          t   r      g ●
 8          ●   ● 
 9              |
10              d
11              ●

The ● marks nodes where a complete word ends. Notice:

cat, car, and card all share the path c → a. The shared prefix is stored once.
car ends at the r node, but the path continues to d for card. That’s why we need an explicit end-of-word flag — a node being a leaf is not the same as a node ending a word.
Looking up any word means walking at most len(word) edges, no matter whether the trie holds ten words or ten million.

That last point is the trie’s superpower. Formally, for a word of length m:

Operation	Trie	Hash Set	Sorted List
Search exact word	O(m)	O(m) average	O(m log n)
Search prefix	O(m)	O(n · m)	O(m log n)
Insert	O(m)	O(m) average	O(n)
All words with prefix	O(m + results)	O(n · m)	O(m log n + results)

A hash set can tell you whether “card” is a word, but ask it “what words start with ‘ca’?” and it has to scan everything. A trie walks two edges and finds the entire answer subtree waiting for it. When a problem says “prefix,” think trie.

The trade-off is space: every node stores a map of children, so a trie of n words of average length m can use O(n · m) nodes in the worst case (no shared prefixes). Real dictionaries share heavily, which is exactly why tries pay off.

Implementing a Trie in Python

Two small classes are all it takes. Each node holds a dictionary of children and a flag; the trie holds the root and three methods.

 1class TrieNode:
 2    def __init__(self):
 3        self.children = {}       # char -> TrieNode
 4        self.is_word = False
 5
 6
 7class Trie:
 8    def __init__(self):
 9        self.root = TrieNode()
10
11    def insert(self, word):
12        """Add a word to the trie. O(m) time."""
13        node = self.root
14        for ch in word:
15            if ch not in node.children:
16                node.children[ch] = TrieNode()
17            node = node.children[ch]
18        node.is_word = True
19
20    def search(self, word):
21        """Return True if the exact word exists. O(m) time."""
22        node = self._walk(word)
23        return node is not None and node.is_word
24
25    def starts_with(self, prefix):
26        """Return True if any word begins with prefix. O(m) time."""
27        return self._walk(prefix) is not None
28
29    def _walk(self, s):
30        """Follow s character by character; None if the path breaks."""
31        node = self.root
32        for ch in s:
33            if ch not in node.children:
34                return None
35            node = node.children[ch]
36        return node

1trie = Trie()
2for word in ["cat", "car", "card", "dog"]:
3    trie.insert(word)
4
5print(trie.search("car"))        # True
6print(trie.search("ca"))         # False — prefix, not a word
7print(trie.starts_with("ca"))    # True
8print(trie.starts_with("do"))    # True
9print(trie.search("care"))       # False

A few implementation notes interviewers appreciate hearing out loud:

Dict vs. fixed array. For a lowercase-only alphabet you could use children = [None] * 26 and index with ord(ch) - ord('a') — faster constant factor, more memory per node. A dict handles any alphabet and skips empty slots. Either is acceptable; say why you chose yours.
The is_word flag is load-bearing. Without it you cannot distinguish “ca” (a prefix on the way to “cat”) from “car” (an inserted word).
search and starts_with share the walk. Factoring _walk out keeps the code tight and shows you spot duplication.

With about 40 lines written, three real interview problems fall open.

Problem 1: Autocomplete (Top-K Suggestions)

Given a dictionary of words, return up to k words that start with a given prefix.

This is the trie’s home turf. Walk to the prefix node in O(m), then DFS the subtree beneath it, collecting complete words until you have k:

 1class AutocompleteTrie(Trie):
 2    def suggest(self, prefix, k=3):
 3        node = self._walk(prefix)
 4        if node is None:
 5            return []
 6
 7        results = []
 8
 9        def dfs(node, path):
10            if len(results) >= k:
11                return
12            if node.is_word:
13                results.append(prefix + path)
14            for ch in sorted(node.children):   # alphabetical order
15                dfs(node.children[ch], path + ch)
16
17        dfs(node, "")
18        return results

1ac = AutocompleteTrie()
2for w in ["car", "card", "care", "careful", "cat", "dog"]:
3    ac.insert(w)
4
5print(ac.suggest("car"))   # ['car', 'card', 'care']
6print(ac.suggest("ca"))    # ['car', 'card', 'care']
7print(ac.suggest("z"))     # []

Complexity: O(m) to reach the prefix, then the DFS touches at most the subtree — with early termination at k results, the work is proportional to output, not dictionary size. Production systems (search engines, IDEs) extend this by storing a precomputed top-k list at each node, trading memory for O(m + k) queries.

The DFS here is plain tree traversal — if the recursion feels shaky, that lesson is the prerequisite.

Problem 2: Word Search II

Given a 2D board of letters and a list of words, find every word that can be formed by tracing adjacent cells (no cell reused within a word).

The brute force — run a separate backtracking search for each word — repeats enormous amounts of work. The trie insight: insert all the words into one trie and walk the board and the trie together. The trie prunes every path the moment it stops matching any word’s prefix.

 1def find_words(board, words):
 2    trie = Trie()
 3    for w in words:
 4        trie.insert(w)
 5
 6    rows, cols = len(board), len(board[0])
 7    found = set()
 8
 9    def dfs(r, c, node, path):
10        ch = board[r][c]
11        if ch not in node.children:
12            return                       # prune: no word continues this way
13        node = node.children[ch]
14        path += ch
15        if node.is_word:
16            found.add(path)
17
18        board[r][c] = "#"                # mark visited
19        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
20            nr, nc = r + dr, c + dc
21            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
22                dfs(nr, nc, node, path)
23        board[r][c] = ch                 # unmark (backtrack)
24
25    for r in range(rows):
26        for c in range(cols):
27            dfs(r, c, trie.root, "")
28    return list(found)

1board = [
2    ["o", "a", "a", "n"],
3    ["e", "t", "a", "e"],
4    ["i", "h", "k", "r"],
5    ["i", "f", "l", "v"],
6]
7print(find_words(board, ["oath", "pea", "eat", "rain"]))
8# ['oath', 'eat']

Complexity: O(R · C · 4^L) worst case, where L is the longest word — but the trie pruning cuts the practical search space dramatically, because most board paths die within two or three characters. This problem is a staple at top-tier companies precisely because it composes two techniques: trie + backtracking. (An optional optimization: delete words from the trie once found, shrinking it as you go.)

Problem 3: Longest Word in Dictionary

Find the longest word that can be built one character at a time, where every prefix of it is also a word in the list. Ties go to the alphabetically smaller word.

Example: with ["w", "wo", "wor", "worl", "world"] the answer is "world" — every step along the way is itself a word.

The trie formulation is elegant: we want the deepest node reachable from the root through word-ending nodes only. BFS handles “deepest” naturally, and visiting children in reverse-sorted order makes the last dequeued answer the alphabetically smallest at max depth:

 1from collections import deque
 2
 3def longest_word(words):
 4    trie = Trie()
 5    for w in words:
 6        trie.insert(w)
 7
 8    best = ""
 9    queue = deque([(trie.root, "")])
10    while queue:
11        node, path = queue.popleft()
12        for ch in sorted(node.children, reverse=True):
13            child = node.children[ch]
14            if child.is_word:            # only step through complete words
15                queue.append((child, path + ch))
16        if len(path) > len(best):
17            best = path                  # BFS: last max-depth pop is smallest
18    return best

1print(longest_word(["w", "wo", "wor", "worl", "world"]))  # "world"
2print(longest_word(["a", "banana", "app", "appl", "ap", "apply", "apple"]))
3# "apple"  ("banana" fails: "b" alone is not a word)

Complexity: O(total characters) to build the trie and O(nodes) for the BFS — linear in the input. The is_word gate does all the conceptual work: "banana" is in the trie, but BFS never reaches it because "b" isn’t a word. If BFS on trees is new to you, Day 20: Graph Traversals covers it.

When to Reach for a Trie in an Interview

A quick trigger list:

The problem mentions prefixes, autocomplete, or “starts with” → trie.
You must match many words simultaneously against something (a board, a stream) → trie as a shared matcher.
You need dictionary lookups where every prefix matters → trie with is_word gating.
You only ever need exact membership → skip the trie; a hash set is simpler and faster in practice.

Tries also underpin fancier structures — suffix trees for substring search and radix trees in routers and databases — but the interview version is exactly the 40-line class above.

Practice It Properly

Reading about tries gets you to “I recognize this”; implementing one from a blank editor gets you to “I can do this in 15 minutes under pressure,” which is what the interview requires. In our 60-day challenge, Day 58 has you build the trie yourself with exercises, right after string algorithms like KMP — and by then you’ll have built every prerequisite from trees to backtracking with your own hands. Sign up free and start with Day 1.

Happy coding — and next time your phone finishes your word, you’ll know exactly what it walked through to do it!