DEV Community

Devanshu Biswas
Devanshu Biswas

Posted on • Originally published at github.com

I built a trie visualizer with live autocomplete — type a prefix, watch the path light up and completions appear

#algorithms #javascript #computerscience #datastructures

Autocomplete feels like magic until you learn the data structure behind it, and then it feels obvious. That structure is the trie (prefix tree). I built an interactive one where you type a prefix and watch the matching path light up and every completion appear.

▶ Live demo: https://dev48v.github.io/trie/
Source: https://github.com/dev48v/trie

The idea

A trie stores strings by their shared prefixes. Every edge is a character; every root-to-node path spells a prefix; a marked node ends a word.

        (root)
        /     \
       c       d
       |       |
       a       o •        ← "do" is a word (• = end-of-word)
      / \     /|\ \
     r   t•  g r t v
    /|\      | | | |
   • e t     • m • e     ← car•, care, cart, dog, dorm, dot, dove
   d
   •
Enter fullscreen mode Exit fullscreen mode

car, card, care, cart all reuse the same c → a → r nodes. That sharing is the whole point: common prefixes are stored once.

Autocomplete is two steps 

autocomplete(prefix):
  node = walk(prefix)          // follow one edge per character
  if !node: return []          // nobody starts with this
  return dfs(node, prefix)     // collect every word in the subtree
Enter fullscreen mode Exit fullscreen mode

Type ca and the demo walks root → c → a (that path highlights), then DFS-collects everything below: cat, car, card, care, cart. No scanning the dictionary — the tree already grouped them.

Why it beats a hash set here

A Set<string> answers "is this exact word present?" in O(1). But it can't answer "what words start with ca?" without scanning every entry. A trie answers both, and its lookup is O(length of the word) — independent of how many words you've stored. A million-word dictionary finds a 5-character prefix in 5 hops. The dataset size never enters the cost.

The details the demo makes concrete

  • End-of-word markers matter. car is a word and a prefix of card. Without a per-node "ends here" flag you couldn't tell "car exists" from "car is just on the way to card." The demo rings those nodes in amber.
  • Delete prunes carefully. Removing car must not break card/care. You unmark the end flag and only delete nodes that have no children and don't end another word. Watch it in the demo: delete car and the shared c → a → r stays because card still needs it.
  • Space vs. speed. Tries trade memory (lots of nodes/pointers) for prefix-query speed. Real-world variants — radix/Patricia tries, DAWGs, ternary search tries — compress the chains to claw back space.

Tries power autocomplete, spell-checkers, IP routing longest-prefix match, and T9 predictive text. Type a few prefixes in the demo and the "how does search-as-you-type work" question answers itself.

If it made tries click, a star helps others find it: https://github.com/dev48v/trie

Top comments (0)