Trie visualizer: prefix tree and autocomplete

Type or paste words into the box, separated by spaces, commas or new lines; the trie is rebuilt as you type. Add a frequency after a colon (app:5) to rank autocomplete suggestions by how often each word is used. Choose an operation and type a word or prefix: the path it walks is highlighted and each step is listed. Insert and Delete change the word list when you press their button.

• Nodes with a double ring end a word. The root is drawn as a dot.
• Switch to Radix tree to see the same words with single-child chains merged.
• Copy answer gives the trie as an indented outline and the steps of the current operation.

A trie, or prefix tree, is a tree for storing strings in which each edge stands for one character and each node for the prefix spelled out on the way down to it. The root is the empty string. A word is stored by following or creating one node per letter and marking the last node as the end of a word, since a word can also be the prefix of a longer one, like "car" in "card".

Because the position of a node already says which prefix it is, a trie never compares whole keys. Finding a word of m letters takes m steps whether the trie holds ten words or ten million.

Insert walks down the word's letters from the root, creating a child wherever one is missing, and marks the final node. Search walks the same way and succeeds only if every letter is found and the final node is marked; reaching an unmarked node means the string is only a prefix of stored words.

Delete unmarks the final node, then removes nodes from the bottom up as long as they have no children and end no other word. In the example car, card, care, careful, cart, cat, dog, do, dot, deleting "careful" removes 3 nodes (the letters f, u and l), while deleting "car" removes 0, because its nodes are still needed by card, care and cart.

Autocomplete is a prefix query: walk down the letters typed so far to one node, then collect every word in the subtree below it. In the example, the prefix "car" leads to a node whose subtree holds car, card, care, careful, cart; the query visits 10 nodes. Real autocomplete ranks the candidates, usually by how often each was searched or typed, and shows the top few; frequencies after a colon in the word list do the same here.

Collecting the whole subtree takes time proportional to its size, which grows when a short prefix matches thousands of words; storing the best few completions at each node in advance avoids the walk, at the cost of memory.

A trie has one node for each distinct prefix of its words, plus the root. The 9 example words have 33 letters but share their beginnings, so the trie needs 14 nodes. The more prefixes words share, the bigger the saving.

Each node also needs a way to find its children. An array with a slot for every letter of the alphabet is fastest, but 26 pointers per node add up quickly, and most slots stay empty; a hash map or sorted list per node saves memory at some cost in speed.

Long chains of nodes with a single child, the tails of words that share nothing with others, waste space. A radix tree (also called a compressed trie, or Patricia trie in its binary form) merges each such chain into one node labelled with several characters. Every remaining node is the root, ends a word, or branches. The example words need 10 nodes this way instead of 14. The 38 reserved words of JavaScript, 191 letters in all, need 158 trie nodes and 54 radix tree nodes.

Tries suit any job that needs prefixes: autocomplete in search boxes and code editors, spell checkers that suggest words sharing a beginning, and word games. Tries over the bits of network addresses can store routing tables, where a lookup must find the longest stored prefix of an address.