Tries

The shape

Every node is one character, and the path from the root spells the prefix. Words that start the same way share their path, which is where the name comes from — it is the middle of "retrieval", and everyone says "try" anyway.

The key insight: a trie is indexed by the shape of the key, not by a hash of it. So it can answer questions about prefixes that a hash table cannot answer at all.

        (root)
        /     \
       c       d
       |       |
       a       o
      / \      |
     r   t*    g*
    / \
   *   t*                  * marks the end of a word

The code is short

end is what separates "car is a word" from "car is on the way to cart". Without it you cannot tell a stored word from a prefix of one.

class Trie {
  #root = { children: new Map(), end: false };

  insert(word) {
    let node = this.#root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, { children: new Map(), end: false });
      node = node.children.get(ch);
    }
    node.end = true;
  }

  #walk(prefix) {
    let node = this.#root;
    for (const ch of prefix) {
      node = node.children.get(ch);
      if (!node) return null;
    }
    return node;
  }

  has(word) { return Boolean(this.#walk(word)?.end); }
  startsWith(prefix) { return this.#walk(prefix) !== null; }
}

The costs, and what they do not depend on

None of them mentions n. Looking up a ten-character word costs the same in a trie of ten words as in a trie of ten million — the work is bounded by the key, not by the collection.

A hash table matches that for exact lookups and is faster in practice, because it touches one bucket instead of walking ten nodes. What it cannot do at any price is the third and fourth rows.

The price: memory

One node per character, each with a Map, is a lot of objects. A trie over a real dictionary can use several times the memory of the strings themselves, which is why the practical variants exist:

• Compressed (radix) trie — a chain of single-child nodes is collapsed into one node holding the whole substring. Far fewer objects, same behaviour.
• DAWG — the compressed trie with identical suffixes shared as well. A dictionary of 300 000 words fits in a few hundred kilobytes.
• Ternary search tree — three children per node instead of one per alphabet character; slower, much smaller.

What it is used for

The word-game case is the one that shows the structure off: a solver walking a board can abandon a path the moment startsWith fails, cutting the search tree by orders of magnitude. Being able to say "nothing can come of this" early is often worth more than the lookup itself.