Trie Builder Screensaver
The Trie Builder screensaver grows a real live prefix tree (trie) branch by branch as random words stream in, sharing common prefixes automatically. It is free, runs in your browser, and ESC exits.
Live preview
Press ESC to leave fullscreen. Settings are saved in your browser only.
How the Trie Builder screensaver works
The saver streams in a real random word, walking the trie one letter at a time from the root.
Wherever a matching letter branch already exists, the real insert reuses it and shares the prefix; only new letters create new branches.
A completed word is marked with a real end-of-word flag on its final node, distinguishing whole words from mere prefixes.
Once the trie reaches a set size, it holds briefly, then clears and a fresh trie begins growing from an empty root.
The prefix tree behind autocomplete
A trie, pronounced either as tree or try, is a tree in which each path from the root spells a prefix of a stored word. Instead of keeping each word as an independent string, words that begin the same way share their opening nodes. Storing cat, car and care takes one shared c-a path and then a small fork. The name comes from the middle syllable of retrieval. René de la Briandais described tries in a computer context in 1959 and Edward Fredkin independently described them in 1960; Fredkin coined the name.
The efficient part is lookup. Searching for a key takes time proportional to the length of the key, not the number of words stored. That makes tries a natural fit for predictive text and autocomplete, spell checking, longest-prefix matching and the IP prefixes in router forwarding tables. A flag on the final node distinguishes a complete word from a mere prefix: car is a word, but ca is not.
The cost is memory. Naive nodes keep an array of child pointers, one per letter, which wastes space when words are sparse. Compressed variants such as radix trees merge chains of single-child nodes. For plain exact-match lookups a hash table is often simpler.
A worked example
The words "cat" and "car" share the real "ca" branch all the way down, only splitting into separate letters at the third character, exactly the structure a real trie produces.
Settings & tips
- Accent recolours the branch currently being extended.
- This is a real, correct trie (prefix tree) implementation.
- The trie clears and regrows automatically once it reaches full size.
Frequently asked questions
- Is this a real trie?
- Yes — a real prefix tree, the same structure behind real autocomplete and spell-check systems.
- Why do branches merge?
- Words that share a real common prefix genuinely reuse the same path through the tree, rather than each getting a separate one.
- Is a key needed?
- No — it is a pure local computation.
- Is it free?
- Yes — free, no download, in your browser.
- What are tries used for?
- They are used for predictive text and autocomplete, spell checking, longest-prefix matching such as IP routing tables, and lexicographic sorting. Anything that asks for all keys beginning with something suits them.
- How is a trie different from a hash table?
- A hash table finds exact keys quickly but has no notion of prefixes or sorted order. A trie supports prefix searches directly, at the price of using more memory.
- What is a radix tree?
- It is a compressed trie in which runs of nodes with only one child are merged into single edges labelled with a string. It saves memory without changing what the structure can do.