python 48 lines · 7 steps

Building a prefix trie in Python

A trie stores words character-by-character in nested nodes so prefix queries and autocomplete become simple tree walks.

Explained by highlit
Intermediate trie tree-traversal recursion prefix-search data-structures
1class TrieNode:
2 __slots__ = ("children", "is_word")
3 
4 def __init__(self):
5 self.children = {}
6 self.is_word = False
7 
8 
9class Trie:
10 def __init__(self, words=None):
11 self.root = TrieNode()
12 for word in words or ():
13 self.insert(word)
14 
15 def insert(self, word):
16 node = self.root
17 for char in word:
18 node = node.children.setdefault(char, TrieNode())
19 node.is_word = True
20 
21 def contains(self, word):
22 node = self._find(word)
23 return node is not None and node.is_word
24 
25 def starts_with(self, prefix):
26 return self._find(prefix) is not None
27 
28 def words_with_prefix(self, prefix):
29 node = self._find(prefix)
30 if node is None:
31 return []
32 results = []
33 self._collect(node, prefix, results)
34 return results
35 
36 def _find(self, prefix):
37 node = self.root
38 for char in prefix:
39 node = node.children.get(char)
40 if node is None:
41 return None
42 return node
43 
44 def _collect(self, node, prefix, results):
45 if node.is_word:
46 results.append(prefix)
47 for char, child in node.children.items():
48 self._collect(child, prefix + char, results)
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1A trie shares common prefixes across words, making prefix lookups proportional to word length rather than dictionary size.
  2. 2Factoring the shared descent into a private _find helper keeps contains, starts_with, and autocomplete tiny and consistent.
  3. 3Recursive collection with an accumulator naturally enumerates every word under a subtree for autocomplete.

Related explainers

python 
from fastapi import FastAPI, WebSocket, WebSocketDisconnect
 
app = FastAPI()
 

Building a WebSocket chat with FastAPI

websockets broadcast connection-management
Intermediate 9 steps
python 
import time
import uuid
 
from django.utils.deprecation import MiddlewareMixin

Attaching per-request context in Django

middleware request lifecycle multi-tenancy
Intermediate 7 steps
javascript 
function evaluate(expression) {
  const tokens = tokenize(expression);
  let pos = 0;
 

Building a recursive descent calculator

parsing recursion operator-precedence
Intermediate 8 steps
python 
import random
from typing import Iterator, List
 
 

How reservoir sampling picks k items

reservoir-sampling streaming randomness
Intermediate 5 steps
python 
import secrets
 
from django.contrib.auth import authenticate, login
from django.core.cache import cache

Two-factor login with OTP in Django

two-factor-auth one-time-passwords caching
Intermediate 9 steps
python 
import re
from functools import total_ordering
from typing import Optional
 

Parsing and comparing semantic versions

regex operator-overloading sorting
Intermediate 7 steps

Share this explainer

Here's the card — post it anywhere.

Building a prefix trie in Python — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code