Pattern visualizer

Implement Trie (Prefix Tree)

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. Animated on: Build a Trie supporting insert, search and startsWith. Insert "cat" and "car", then run search("car"), search("ca") and startsWith("ca")..

One node per character, shared prefixes share nodes

time O(L) per operationspace O(total characters)step 1 / 12

•

line 1

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

Where to practice Trie

Practice Trie problems All Trie problems Back to roadmap