Trie (prefix tree)

Store words by their shared prefixes so lookup costs the length of the word, not the size of the dictionary. This is what sits behind autocomplete and spell-checking.

time O(length) per insert or lookup

space O(total characters)

Input

Press Tab out of the box or click Resetto regenerate frames from the current input.

Visualization

No frames yet — edit input and click Run.

—

Pseudocode

insert(word):
  node = root
  for ch in word:
    if ch not in node.children: node.children[ch] = new Node()
    node = node.children[ch]
  node.isEnd = true