juniorTrie

What is a trie and when would you use one?

Updated Feb 20, 2026

Short answer

A trie is a tree where each edge carries a character and each path from the root spells a prefix, so strings sharing a prefix share the same nodes. Lookup and insertion cost O(k) in the key length, independent of how many keys are stored. Its real advantage over a hash table is prefix queries — finding every word starting with 'inter' is a single subtree walk.

Deep explanation

Python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False        # marks the END of a stored word


class Trie:
    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True


    def starts_with(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return []
            node = node.children[ch]
        return self._collect(node, prefix)     # walk the subtree
TypeScript
root
         |c
         a
       /a  \o
      r      t          "car", "cart", "cat" share "ca"
      |t

The is_word flag is essential and easy to forget. Without it there is no way to distinguish a stored word from a mere prefix of one — "car" would look identical to the path passing through on the way to "cart".

Costs. Lookup and insert are O(k), independent of n. A hash table is O(k) too, since it must hash the whole key — so a trie is not faster for exact lookup, and in practice is usually slower due to pointer chasing and poor cache locality.

What a trie has that a hash table does not:

  • Prefix search — all keys under a prefix is one subtree traversal.
  • Ordered iteration — a depth-first walk yields keys in lexicographic order.
  • Longest-prefix matching — the basis of IP routing tables.
  • No collisions, and no worst-case degradation from adversarial keys.

The real cost is memory. A node per character, each holding a map of children, is heavy. Storing a million words with little shared prefix means millions of nodes. Compressed variants — radix trees, which merge chains of single-child nodes — cut this substantially, and are what production routing tables and databases actually use.

Real-world example

Search autocomplete, where the hash table simply cannot help:

Python
trie = Trie()
for term in search_terms:          # 5,000,000 historical queries
    trie.insert(term)


trie.starts_with('inter')
# ['interview', 'interest', 'internet', 'interval', ...]

The trie walks five nodes to reach the inter subtree, then collects beneath it — proportional to the number of results, not to the five million stored terms. A hash table would have to scan every key to test the prefix, since hashing deliberately destroys the relationship between similar strings.

Common mistakes

  • - Omitting the end-of-word flag, making a stored word indistinguishable from a prefix of a longer one.
  • - Claiming a trie is faster than a hash table for exact lookup — both are O(k), and the hash table usually wins on cache behaviour.
  • - Underestimating memory. A naive trie with a fixed 26-pointer array per node wastes enormous space on sparse data
  • a dictionary of children is far leaner.
  • - Deleting a word by removing nodes without checking whether they are shared — removing 'car' must not break 'cart'.
  • - Reaching for a trie when only exact membership is needed
  • without prefix or ordering requirements, a hash set is simpler and faster.

Follow-up questions

  • How does a trie compare to a hash table for exact lookup?
  • How do you delete a word from a trie?
  • What is a radix tree?
  • How is a trie used for longest-prefix matching?

More Trie interview questions

View all →