Trie Generator
A trie stores every shared prefix exactly once, which is why autocomplete uses one: finding every word starting with "car" costs three steps and then a walk, no matter how many words are stored. The subtlety worth checking is that a trie can quietly hold words nobody inserted — a prefix marked terminal by mistake looks identical from outside — so this verifies both that every inserted word is found and that nothing else is.
What this generator does
Inserts words drawn from a set chosen to share prefixes heavily, then reports the node count against what storing each word separately would cost, and lists the prefixes more than one word shares.
How to use this tool
- Choose how many words to insert.
- Count how many nodes a plain list would need against what the trie uses.
- Look at the shared prefixes, which are stored once each.
- Copy the word list to build the trie yourself.
Understanding the controls
- How many words
- Between 4 and 30, drawn from a fixed vocabulary built around three prefix families so overlaps are guaranteed.
- Seed
- Reproduces the same word set exactly, so a trie can be set as an exercise and marked later.
Common use cases
- Worked trie examples with the storage saving quantified
- Showing why prefix search is cheap and suffix search is not
- Test data for an autocomplete implementation
- Teaching the difference between a stored word and a mere prefix
- Reproducing the same word set from a seed
How this generator works
Insertion walks or creates one node per character and marks the last as terminal. The check runs in both directions: every inserted word must be findable, and the words collected by walking every path to a terminal node must be exactly the words inserted — no more and no fewer.
Randomness and fairness
Which words are drawn is random; the structure follows from them. Seeded tries reproduce exactly and are therefore explicitly not cryptographically secure, and unseeded ones use the browser's cryptographically secure generator.
For how randomness is produced across the whole site, see how Generate Random works.
Limitations and good to know
- Words come from a fixed vocabulary of thirty, so sets repeat at the larger sizes.
- No compression — a radix tree collapsing single-child chains would use far fewer nodes.
- Deletion is not demonstrated, and it is the operation that needs care.
- The trie is summarised by counts and prefixes rather than drawn as a tree.
- Tries are not stored between visits.
Privacy and your data
Words and the trie are held only in your browser. Nothing about the set or your seed is transmitted or stored.
Related generators
- Binary Heap GeneratorMin or max heaps built one insertion at a time, shown level by level, and drained to prove they sort.
- Binary Search Tree GeneratorAn insertion order and the tree it builds, with all three traversals, the height, and whether it came out balanced.
- Word Ladder GeneratorWord ladders where every rung is checked against a published word list, and the answer is the shortest path that exists.
- Hash Table Scenario GeneratorKeys distributed into buckets by modulo hashing, with collisions, chain lengths and empty buckets all recounted from the table.