Trie (Prefix Tree)

Medium

Words that share a prefix share a path. Lookup costs the length of the word, no matter how large the dictionary grows.

prefix sharingdictionary

TimeO(word length) per operation

SpaceO(total characters)

InputComma separated words

Start with an empty root. Each edge is one character.

1 / 24

insert(word):

node = root

for ch in word:

if ch not in node.children: create it

node = node.children[ch]

node.isWord = true

Why it matters

Autocomplete, wildcard search and maximum XOR pairs are all tries underneath.

Practise this

Keyboard

space play← → stepr restartctrl K search