TreesTrees

Trie (Prefix Tree)

A tree keyed by characters where each root-to-node path spells a prefix, giving O(L) insert, lookup and prefix search independent of how many words are stored.

Learn Trie →

Commands — insert W, search W, startsWith W — lowercase words, comma separated

1/43Empty trie: only the root. Each edge holds one character, and a node with the "end" badge terminates a stored word.

Matched prefixCurrent nodeNew nodeMatch / word end

PseudocodeLearn Trie →

1node = root
2for ch in word:
3  if ch not in node.children: (insert) create child / (search) return false
4  node = node.children[ch]
5insert: node.end = true
6search: return node.end
7startsWith: return true

Variables

words0

Complexity

access —

search O(L)

insert O(L)

delete O(L)

Speed