Implement Trie (Prefix Tree)

One node per character, shared prefixes share nodes

time O(L) per operationspace O(total characters)

A trie is a tree where every edge is one character and the path from the root spells a prefix. Words with the same prefix walk the same nodes, so every operation costs O(length of the word) — the size of the dictionary never matters. A node needs an END flag: "ca" exists as a path inside "cat", but it is only a word if something marked it so.

Details

Animated on: Build a Trie supporting insert, search and startsWith. Insert "cat" and "car", then run search("car"), search("ca") and startsWith("ca").

Problem:Implement Trie (Prefix Tree)Medium

Pattern:Trie

One node per character, shared prefixes share nodes

step 1 / 12

•

Start with an empty trie: just a root node that spells the empty prefix. It holds no character itself.

Pseudocode

1node = { children: {}, end: false }
2FUNCTION insert(word):
3  cur = root
4  FOR ch IN word:
5    IF ch NOT IN cur.children: cur.children[ch] = new node
6    cur = cur.children[ch]
7  cur.end = true
8FUNCTION search(word):
9  cur = walk(word)        // follow each char; null if a link is missing
10  RETURN cur != null AND cur.end
11FUNCTION startsWith(prefix):
12  RETURN walk(prefix) != null

← / → step · space play · Home restart

Every step in words

Show all 12 steps

Start with an empty trie: just a root node that spells the empty prefix. It holds no character itself.
insert("cat"): begin at the root. The first character is c — the root has no c child yet, so create one and step into it.
Next character a. Node c has no a child, so create it and move down. The path root → c → a now spells the prefix "ca".
Last character t: create it, then mark it as an END node (double ring). Without that flag the trie would only know "cat" as a path, not as a word.
insert("car"): back at the root, c already exists — follow the existing link instead of creating anything.
a exists under c too, so follow it. Two words are now sharing the same two nodes — this sharing is the whole point of a trie.
r is missing under "ca", so create it as a second child next to t and mark it END. The trie now holds cat and car in 4 nodes instead of 6.
search("car"): walk c → a → r, following existing links only. Every link exists.
The walk ended on a node whose END flag is set, so search returns TRUE — "car" was stored as a whole word.
search("ca"): walk c → a. The path exists, so the walk succeeds and stops on node a.
But node a is NOT an end node — "ca" is only a prefix of cat and car, never inserted as a word. search returns FALSE.
startsWith("ca"): the same walk c → a succeeds, and here the END flag is irrelevant — a prefix only needs the path to exist. Returns TRUE.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Implement Trie (Prefix Tree) in the editor All Trie problems Back to roadmap