Trie (Prefix Tree)

A trie (also called a prefix tree) stores strings as *paths of letters* branching out from a single root. Follow the edges t-r-e-e and you have spelled "tree". The defining win: words that begin the same way share the same early path, so a whole dictionary folds into one compact tree, and a lookup costs only as many steps as the word is long — never how many words are stored.

Anatomy of a trie

1. 1The root is an empty starting node; every word's path begins here.
2. 2Each edge is labelled with one character; walking edges down spells out a string.
3. 3A node carries a word-end marker — a flag meaning 'a complete word ends here'.
4. 4Two words with a shared prefix share every node up to where they diverge.

Worked example — insert car, card, cat

(root)
  |
  c
  |
  a
 / \
r   t*        (* = word-end marker)
|
d*

stored: car* (c-a-r), card* (c-a-r-d), cat* (c-a-t)
the shared prefix "ca" is stored exactly once.

Searching for cart: walk c -> a -> r, then look for a t edge below r. There is none, so cart is absent — and we discovered that in 4 steps, regardless of how many thousands of other words the trie holds.

function search(root, word) {
  let node = root;
  for (const ch of word) {
    node = node.children[ch];
    if (!node) return false;   // path falls off the trie
  }
  return node.isWord;          // reached the end: is it a stored word?
}