Tries Explained: Follow a Prefix One Character at a Time

By Hourly DSA · October 3, 2026 · 4 min read

A trie stores strings along character paths, letting words with the same prefix share the beginning of their route. It is useful when a question asks about starts-with matching rather than only exact membership.

A small dictionary shows why that difference changes the data structure you might choose.

Insert car, cart, and cat. Starting at the root, each word follows c and then a. After that, the paths branch:

root
  c
    a
      r (word)
        t (word)
      t (word)

Each edge consumes one character. The marks identify where complete words end.

The words do not need separate copies of the c–a path. Inserting cart can reuse the existing path for car and extend it by one character.

A path is not necessarily a word

Searching for ca reaches a node, so at least one stored word begins with that prefix. But ca is not in our dictionary because its node has no word-ending mark.

Searching for car reaches a marked node, so it is a complete word. That node also has a child because cart continues farther.

This is the common misconception: a word does not have to end at a leaf. If you only mark leaves as words, storing cart would make you lose track of car.

Exact lookup needs both a matching path and a terminal mark. Prefix lookup only needs the matching path.

Trace a failed search

Try the prefix cab. The c and a edges exist, but there is no b edge next. You can stop immediately: no word below this point can match the requested prefix.

You don't need to compare cab against every complete word. The shared structure narrows the search as each character is consumed.

For a query of length L, traversal takes O(L) time if each child lookup takes O(1). Fixed-alphabet arrays can provide that lookup; hash maps typically provide expected constant-time lookup. The representation is part of the complexity assumption.

Finding suggestions costs more than finding a prefix

Reaching the node for ca tells you matching words exist. Listing them requires exploring descendants and emitting car, cart, and cat.

That additional work depends on the subtree visited and the amount of text returned. An O(L) prefix check does not imply that returning thousands of suggestions also takes O(L).

Likewise, a basic trie does not automatically rank suggestions by popularity. It organizes prefixes. Ranking or limiting results requires an additional rule and possibly additional stored information.

Compare it with a hash set

If you only need to ask whether a complete word exists, a hash set is often simpler. Hashing a string still requires reading its characters, even when the subsequent table lookup is expected constant time.

A trie becomes a stronger candidate when many queries share prefix structure, or when you need to walk through possible next characters.

Its tradeoff is memory. With S total inserted characters, there are at most S + 1 nodes, including the root. Each node also needs child storage and a terminal flag. Large child arrays can waste space when most slots are empty.

Deleting a word should preserve its neighbors

Suppose you remove car but keep cart. Clear the terminal mark at r, but preserve its path: cart still needs it.

Pruning is safe only when a node is not terminal and has no remaining children. Removing an entire prefix path just because one word was deleted can erase other words accidentally.

Test the terminal mark

After deleting car, what should exact lookup for car return? What about prefix lookup?

Exact lookup is false; prefix lookup is true. The path remains for cart, but r no longer ends a stored word.

Try changing one word and predicting which answers change. That is the kind of small data-structure trace you can practice with Hourly DSA.