Tries Explained Simply (With Real Interview Problems)

· Written by

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:

OperationTrieHash SetSorted List
Search exact wordO(m)O(m) averageO(m log n)
Search prefixO(m)O(n · m)O(m log n)
InsertO(m)O(m) averageO(n)
All words with prefixO(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!