Trie

First PublishedFeb 11, 2026ByAtif Alam

Difficulty: Medium. ROI: Low.

Other common names: Prefix tree, digital tree, radix tree (when compressed).

When to use: Use when you need to store strings and support prefix lookups, “all keys with prefix X,” or word search in a grid. Good for autocomplete and dictionary-style problems.

Idea: Each node has children keyed by the next character. A path from the root spells a prefix; mark nodes where a word ends. Insert and search are O(m) for a string of length m.

Time / space: Insert and search O(m) per string. Space O(total characters in all strings) in the worst case.

Example #1 — Trie Insert and Search

Store strings in a tree where each edge is a character; a path from the root spells a prefix. Mark nodes where a word ends so we can distinguish full words from prefixes.

Sample input and output

1
t = Trie()
2
t.insert("cat")
3
t.insert("cats")
4
t.insert("car")
5
print(t.search("cat"))   # True
6
print(t.search("ca"))   # False (prefix only)
7
print(t.search("dog"))  # False

Sample input: Insert “cat”, “cats”, “car”; then search “cat”, “ca”, “dog”.
Sample output: True, False, False — “cat” is a stored word; “ca” is only a prefix; “dog” is not in the trie.

Code (with inline comments)

1
class TrieNode:
2
    def __init__(self):
3
        self.children = {}   # map next character -> child TrieNode
4
        self.is_end = False  # True if a word ends at this node
5

6
class Trie:
7
    def __init__(self):
8
        self.root = TrieNode()
9

10
    def insert(self, word):
11
        node = self.root
12
        for c in word:
13
            if c not in node.children:
14
                node.children[c] = TrieNode()
15
            node = node.children[c]   # step down into the child
16
        node.is_end = True   # mark end of this word
17

18
    def search(self, word):
19
        node = self.root
20
        for c in word:
21
            if c not in node.children:
22
                return False
23
            node = node.children[c]
24
        return node.is_end   # must end at a word, not just a prefix

Line-by-line:

self.children = {} — Each node has a dict mapping a single character to the next node. Following a path from the root spells a prefix; different branches correspond to different words/prefixes.
self.is_end = False — We set this to True only at nodes where a complete word ends (so “cat” and “cats” share the path c→a→t, but only the “t” node for “cat” has is_end=True if we inserted “cat”).
node = self.root — Start at the root for each insert or search.
if c not in node.children: node.children[c] = TrieNode() — If there’s no edge for this character, create a new node. Then step to that child with node = node.children[c].
node.is_end = True — After processing all characters, we’re at the node that represents this full word; mark it so we can distinguish “cat” from “cats” (prefix only).
return node.is_end — We only return True if we followed the whole word and ended at a node marked as an end-of-word (not just a prefix).

Execution trace (numbered list)

Step 1: insert(“cat”). root → c → a → t, mark t.is_end=True.
Step 2: insert(“cats”). Follow c→a→t, add child ‘s’, mark s.is_end=True.
Step 3: insert(“car”). Follow c→a, add child ‘r’, mark r.is_end=True.
Step 4: search(“cat”). Follow c→a→t, return t.is_end → True.
Step 5: search(“ca”). Follow c→a, return a.is_end → False.

Execution trace (code with step comments)

1
# insert("cat"): root -c-> -a-> -t-> (is_end)
2
# insert("cats"): follow to t, add -s-> (is_end)
3
# insert("car"): follow c->a, add -r-> (is_end)
4
# search("cat"): c->a->t, is_end=True → True
5
# search("ca"): c->a, is_end=False → False

Execution trace (ASCII diagram)

Trie after inserting “cat”, “cats”, “car”. * marks end-of-word.