---
title: "Trie"
description: "Prefix tree for fast string lookup"
source: https://vizlearn.app/algorithms/data-structures/trie
access: premium (interactive player requires Lifetime; this doc is free)
---

# Trie

A trie is a tree-shaped data structure behind autocomplete and prefix routing. It stores strings by shared prefixes, with one character per edge. Insert, exact search, and prefix search run in O(L) time for a length-L query; a word-end marker separates complete words from paths that are merely prefixes.

Picture an office corridor where each door adds one letter to the room number. `car` and `cat` walk through the same `c` and `a` doors, then split at `r` and `t`. Reaching a door proves the prefix exists. The small nameplate on that door proves someone actually occupies the room.

## One edge per character in a trie

The root stores no character. Its children are keyed by the first character of each word; every later node maps the next possible character to another child. A node therefore represents the full prefix along the path from the root. The node labelled `a` under `c`, for example, represents `ca`, not every `a` in the structure.

`insert(word)` starts at the root and reads the word from left to right. If the current node already has a child for the next character, insertion reuses it. If the child is missing, insertion creates one. After the last character, it sets the final node's word-end marker. That last write matters more than it looks: the path `c -> a` may exist because `car` is stored, but `ca` is not automatically a word.

Both query operations use the same character walk. `search(word)` returns true only when the whole path exists and the final node has a word-end marker. `startsWith(prefix)` asks a weaker question: did the walk consume every character? It does not care whether the endpoint is a complete word. In the corridor picture, `startsWith("ca")` reaches the right door; `search("ca")` also checks the nameplate.

That distinction is the trie's entire personality. The tree answers prefix questions naturally because every prefix is already a physical path. Exact membership needs one extra bit at the endpoint. A trie is fussy about that bit, and the bit earns its keep.

## Trie step by step

The default run starts with an empty root and performs five operations.

1. `insert("car")` reads `c`, `a`, then `r`. None of those children exists, so the trie creates three character nodes and advances into each one. It then marks `r` as a word end. The structure now stores one word, three stored characters, and three character nodes.

2. `insert("cat")` reads `c` and finds the existing `c` child. It reads `a` and reuses that child too. Only `t` is missing, so this insertion allocates one new node, advances into it, and marks it as a word end. The two words contain six characters in total, but the trie uses four character nodes: `c` and `a` are stored once, then the path branches to `r` and `t`.

3. `search("car")` follows the existing `c`, `a`, and `r` edges. The final `r` node carries a word-end marker, so exact search returns true.

4. `startsWith("ca")` follows `c` and `a`. Both edges exist, so prefix search returns true. The `a` node has no word-end marker, but this operation never asked for one.

5. `search("ca")` follows the same two edges and reaches the same `a` node. Exact search checks the missing word-end marker and returns false. Same path, different contract.

On the canvas, the current character and edge carry the strong amber signal. The matched prefix stays visible at medium weight while unrelated branches fade back. A check-ring marks complete words; the final two operations differ only in whether the algorithm requires that ring.

## Time and space complexity

Let L be the number of characters in the word or prefix being processed.

| Operation            | Time complexity | Extra space                               |
| -------------------- | --------------- | ----------------------------------------- |
| `insert(word)`       | O(L) average    | O(L) worst case for newly allocated nodes |
| `search(word)`       | O(L) average    | O(1)                                      |
| `startsWith(prefix)` | O(L) average    | O(1)                                      |

These bounds assume each node's child map supports average O(1) lookup, as Python dictionaries and JavaScript `Map` objects do. A trie does not search through its stored words. It reads the query once and lets each character choose exactly one outgoing edge. Calling that O(1) because the child lookup is hashed is a classic accounting trick: you still have to consume L characters.

The **Many words** scenario makes the independence from word count visible. It stores eight words, then runs `search("cap")`. The query still follows three edges: `c`, `a`, and `p`. The word count has climbed to eight; the work is still set by the three-character query.

Total storage is O(P), where P is the number of distinct non-empty prefixes across all stored words. Shared prefixes make P smaller than the total number of stored characters. With `car` and `cat`, P is 4 while the words contain 6 characters. If the words share nothing, P reaches the total character count and the trie saves no nodes. The **No sharing** scenario demonstrates that memory breaking point with `ant`, `boy`, and `cup`: nine characters, nine character nodes.

If you only need exact membership, a hash set is usually the simpler choice and often uses less memory. Pick a trie when prefix queries are part of the product: autocomplete, prefix routing, or listing every key under `ca`. You pay for that ability with a child map at every node and less cache-friendly memory access.

The player limits the drawing to 24 character nodes and words of length 6 so labels remain readable. That is a canvas limit, not a property of tries. A real trie keeps growing until memory runs out or the application imposes its own policy.

## Edge cases

- **Empty trie:** `search` and `startsWith` fail on the first character because the root has no matching child.
- **One-character word:** the root points directly to one node, and that node's word-end marker decides exact membership.
- **Duplicate insert:** inserting an existing word reuses every node and sets an already-true marker. Node count, word count, and stored-character count stay unchanged.
- **A word that is also a prefix:** after inserting `car` and `care`, the `r` node is terminal and still has an `e` child. Nodes may be both complete words and internal prefixes.
- **Little or no prefix sharing:** the trie remains correct and lookup stays O(L), but its memory advantage disappears because almost every character needs its own node.

## Common mistakes

- **Treating every reachable path as a word.** That makes `search("ca")` return true after inserting `car`. Exact search must check the final word-end marker.
- **Checking the marker in `startsWith`.** Prefix search only needs the path. Requiring a terminal node turns it into exact search with a misleading name.
- **Advancing before creating a missing child.** On insertion, allocate `children[ch]` first, then move `node` into it. Reversing those lines dereferences a child that does not exist.
- **Counting the structural root as a character node.** The root is a routing anchor and stores no character. Storage comparisons should count the non-root prefix nodes.
- **Claiming every trie operation is O(1).** Child selection is average O(1), but a word of length L performs that lookup L times. The operation is O(L).