Trie (prefix tree)

O(L) per word

A trie (prefix tree) is a tree where each edge is labelled with a character and a path from the root spells out a prefix. Words that begin the same way share the same nodes — "car", "card" and "cat" all share the "ca" path — and a node is flagged (green ring here) when a complete word ends there. Inserting or searching a word just walks down one character at a time, so it costs O(L) for a word of length L, no matter how many words are stored. The trade-off is memory, since every distinct prefix gets its own nodes. Tries power autocomplete, spell-checkers, IP routing, and dictionary lookups. A search ends in one of three ways: the word is found (it ends on a flagged node), it's only a prefix of stored words (path exists, no flag), or it's absent (the path breaks).

Words Search

Prefix tree

Press ▶ to run

Edit the input and press Play

Loop

How it works

To insert a word, start at the root and follow one edge per character.
If the edge for a character doesn't exist yet, create the node.
Mark the final node as the end of a word (the green ring).
To search, walk the characters — found only if they all exist and the last node is flagged.

Pseudocode

1trie:                               # O(L) per word2  insert(word):3    start at the root4    for each char: follow the child edge, or create it5    mark the final node as end-of-word6  search(word):7    walk the chars from the root8    found if every char exists AND the last node is end-of-word