Trie: Why Does the Search Box Always Know What You're Typing?

When you type the first few letters into a search box, the interface can often suggest useful completions almost immediately. Type ca, for example, and it may recognize that words such as car, card, care, and cat are possible matches.

A data structure called a Trie, commonly pronounced “try,” is designed around this exact pattern. A Trie is also known as a prefix tree because it stores strings by their prefixes. Instead of treating each word as one indivisible value, it stores a word one character at a time. Words that begin with the same characters share the same path through the structure. When their characters differ, the path branches.

That simple idea gives a Trie a natural way to answer prefix-oriented questions:

• Does this complete word exist?
• Does any stored word begin with this prefix?
• Which words continue this prefix?
• Where should an autocomplete lookup begin?

This article explains how a Trie is built, how an autocomplete query follows its lookup path, why an end-of-word marker is necessary, what the main operations cost, and which implementation details matter in practice.

The central idea: share prefixes​

Consider this collection of words:

car
card
care
cat
dog

A simple list stores five separate strings. A Trie organizes them according to their common beginnings.

The words car, card, and care all begin with car. Their paths can therefore share the nodes for c, a, and r. After r, the paths diverge:

• car ends.
• card continues with d.
• care continues with e.

The words car and cat share the prefix ca, but they differ at the third character. One branch continues with r, while the other continues with t.

The word dog has no initial character in common with these words, so it starts on a separate branch from the root.

A conceptual representation looks like this:

root
├── c
│   └── a
│       ├── r  [word: car]
│       │   ├── d  [word: card]
│       │   └── e  [word: care]
│       └── t  [word: cat]
└── d
    └── o
        └── g  [word: dog]

The exact drawing is less important than the structure behind it:

1. Every edge represents a character.
2. A path from the root spells a prefix or complete word.
3. Shared prefixes use shared nodes.
4. Branches appear when words require different next characters.
5. A marker identifies where a complete word ends.

The root does not represent a character. It represents the empty prefix, before any characters have been consumed.

What a Trie node contains​

A basic Trie node normally stores two types of information:

1. Child links: references to nodes representing characters that can follow the current prefix.
2. An end-of-word marker: a Boolean value indicating whether a complete stored word ends at this node.

A node might be described conceptually as follows:

TrieNode:
    children: mapping from character to TrieNode
    isWord: Boolean

Suppose the Trie contains car, card, and care. The node representing car has isWord = true, but it also has children for d and e. This is an important detail: a node can be both the end of a complete word and the beginning of longer words.

Without the end marker, the structure could tell us that the path c → a → r exists, but it could not tell us whether car itself was stored. The path might only exist because longer words such as card and care were inserted.

The marker separates two different questions:

• Does this path exist? This is a prefix question.
• Does a complete word end here? This is an exact-word question.

Why a Trie is useful for autocomplete​

Autocomplete is not primarily asking whether the exact string typed by the user is a complete word. If the user types ca, the application wants to find words that begin with ca.

In a Trie, ca corresponds to a specific node reached by following two character links:

root → c → a

Once the lookup reaches that node, the descendants below it represent possible continuations. In the example collection, the relevant subtree contains paths for:

• car
• card
• care
• cat

The branch for dog is unrelated because it begins with d, not ca.

This gives autocomplete a clear two-stage process:

1. Follow the typed prefix from the root.
2. Explore the subtree below the prefix node to find complete words.

The first stage identifies the matching region. The second stage collects the suggestions.

Building a Trie one word at a time​

A Trie is usually built incrementally. Start with an empty root node, then insert each word character by character.

To insert a word:

1. Set the current node to the root.
2. Read the word from left to right.
3. Check whether the current node already has a child for the next character.
4. If the child does not exist, create it.
5. Move to that child.
6. Repeat until all characters have been processed.
7. Mark the final node as the end of a complete word.

For the word car, the path is:

root → c → a → r

After the final character is processed, the r node is marked as a complete word.

Inserting the first word​

Assume the Trie is empty and we insert car.

At the root, there is no c child, so create one. At the c node, there is no a child, so create one. At the a node, there is no r child, so create one. Finally, mark the r node as terminal.

The structure is now:

root
└── c
    └── a
        └── r  [word: car]

Inserting a word that extends an existing word​

Now insert card.

The nodes for c, a, and r already exist, so insertion reuses them. Only a new d child is needed below r:

root
└── c
    └── a
        └── r  [word: car]
            └── d  [word: card]

The existing end marker for car must remain. Adding a longer word does not make the shorter word disappear.

Inserting another word with the same prefix​

Next insert care. Again, the path c → a → r already exists. The r node receives a new e child, which is marked as the end of care.

At this point, the r node has three important properties:

• It represents the prefix car.
• It is marked as the end of the word car.
• It has children for longer words card and care.

This combination is completely valid and common in a Trie.

Inserting a word that branches earlier​

Now insert cat. The path c → a exists, but the a node does not have a t child. Create that child and mark it as a complete word:

root
└── c
    └── a
        ├── r  [word: car]
        │   ├── d  [word: card]
        │   └── e  [word: care]
        └── t  [word: cat]

The shared c → a path is reused, while the different third character creates a branch.

Inserting a word with no shared beginning​

Finally insert dog. The root has no d child, so insertion creates a new branch:

root
├── c
│   └── a
│       ├── r  [word: car]
│       │   ├── d  [word: card]
│       │   └── e  [word: care]
│       └── t  [word: cat]
└── d
    └── o
        └── g  [word: dog]

Insertion pseudocode​

The basic insertion algorithm is short:

insert(word):
    node = root

    for character in word:
        if character is not a child of node:
            node.children[character] = new TrieNode()

        node = node.children[character]

    node.isWord = true

The important operation is reuse. If the required child already exists, follow it. Do not replace it with a new node, because that could disconnect words that were inserted earlier.

The end marker is assigned only after the complete word has been consumed. Marking a node too early would incorrectly treat a prefix as a complete word.

Exact-word search​

A Trie can search for a complete word by following the same character path used during insertion.

Suppose the Trie contains only card, and we search for car. The lookup successfully follows:

root → c → a → r

However, the r node is not marked as the end of a word. Therefore, car is not stored as a complete word. It is only a prefix of card.

The exact search algorithm is:

1. Start at the root.
2. For every character in the query, follow the matching child.
3. If a required child is missing, return false.
4. After all characters are consumed, return the final node's isWord value.

Pseudocode:

contains(word):
    node = root

    for character in word:
        if character is not a child of node:
            return false

        node = node.children[character]

    return node.isWord

This final check is what distinguishes exact search from prefix search. Finding a path proves that the query is a prefix of at least one inserted word, but it does not prove that the query itself was inserted.

Prefix lookup​

Autocomplete begins with a prefix lookup rather than an exact-word lookup.

Suppose the user types ca. The algorithm follows the path:

root → c → a

If the c child does not exist, no stored word can begin with ca. The search can stop immediately. Similarly, if c exists but has no a child, there are no matches for ca.

If the complete path exists, the lookup returns the node representing ca:

findPrefixNode(prefix):
    node = root

    for character in prefix:
        if character is not a child of node:
            return nothing

        node = node.children[character]

    return node

This function does not necessarily return suggestions. It returns the location from which suggestions can be collected.

That distinction keeps the algorithm clear:

• findPrefixNode answers, “Does this prefix path exist, and where does it end?”
• A descendant traversal answers, “Which complete words are below this node?”

Collecting autocomplete suggestions​

After finding the node for a prefix, traverse its descendants. During the traversal, keep track of the characters that form the current path.

For the prefix ca, begin with currentText = "ca". If the traversal moves to a child labeled r, the current text becomes car. If that node is marked as a word, emit car. Continuing to d produces card; continuing to e produces care.

A recursive collection procedure can be written as:

collect(node, currentText, results):
    if node.isWord:
        add currentText to results

    for each character and child in node.children:
        collect(child, currentText + character, results)

The complete autocomplete operation becomes:

autocomplete(prefix):
    node = findPrefixNode(prefix)

    if node does not exist:
        return empty list

    results = empty list
    collect(node, prefix, results)
    return results

For the stored words car, card, care, cat, and dog, the query ca reaches the node for ca. Traversing below it finds four terminal paths:

car
card
care
cat

The path for dog is never explored because it is outside the ca subtree.

Tracing the autocomplete lookup path​

It is useful to follow a query step by step.

Assume the stored words are:

car
card
care
cat
dog

The user types ca.

Step 1: begin at the root​

The root represents the empty prefix. The first query character is c, so the lookup checks for a c child. That child exists, and the current node becomes the node representing c.

Step 2: consume the second character​

The next query character is a. The current c node has an a child, so the lookup follows it. The current node now represents the complete prefix ca.

Step 3: stop consuming query characters​

All characters in the query have been consumed. The lookup does not need to examine the root's other branches. The node for ca identifies the exact subtree containing the possible completions.

Step 4: explore the first continuation​

The ca node has a child labeled r. Following that edge produces car. Because the r node is terminal, car is a suggestion.

That same node has children for d and e:

• r → d produces card, which is terminal.
• r → e produces care, which is terminal.

Step 5: explore the other continuation​

The ca node also has a child labeled t. Following it produces cat, which is terminal.

The resulting suggestions are:

car
card
care
cat

This is the structural reason a Trie matches autocomplete so naturally: the typed prefix is represented by a path, and its possible completions are complete words reachable below that path.

Prefix lookup and result collection are different costs​

Let L be the length of the string being inserted or searched.

The path-following part of insertion examines each character once, so its time complexity is O(L). Exact search also follows at most one child per query character, giving O(L). Finding the node for a prefix likewise costs O(L).

The basic operation costs are therefore:

Insert:          O(L)
Exact search:    O(L)
Prefix lookup:   O(L)

Autocomplete has an additional phase. Once the prefix node is found, the algorithm may need to traverse a large subtree. The total work includes both the prefix path and the requested result collection:

cost of following the prefix
+ cost of exploring and producing completions

If a prefix matches many words, the traversal has more information to inspect and potentially more results to return. No algorithm can return an arbitrarily large result set without doing work proportional to the output it produces.

The number of nodes in a Trie depends on how much prefix sharing exists among the stored strings. Words with common beginnings reuse nodes. Words with unrelated beginnings create separate branches. The structure takes advantage of common prefixes, but it still needs nodes and child links for the character paths it represents.

The details of child storage also affect practical performance. The abstract Trie operation assumes that a node can locate a child for a given character. The cost and memory behavior of that lookup depend on whether children are stored in a mapping, an array, or another collection.

How a Trie represents prefixes by depth​

A Trie node's depth corresponds to the length of the prefix it represents.

For the word cat:

root → c → a → t

The nodes represent:

root: empty prefix
c:    c
 a:   ca
t:    cat

This interpretation makes the tree more than an arbitrary arrangement of nodes. Each location has a string meaning. Reaching a node means that the corresponding prefix has been consumed.

The root represents the empty prefix. An application could use the root's end marker to represent the empty string, although many basic uses do not store an empty word. The important point is that the root naturally provides the starting position for every lookup.

Choosing a child representation​

Every Trie node needs a way to associate a character with its child node. A common conceptual representation is a mapping:

node.children[character] = childNode

A mapping is flexible when the possible character set is large or when most nodes have only a few children. Each node stores links for the characters that actually occur below that prefix.

Another option is an array indexed by character values. For a fixed and compact alphabet, this can provide direct access by index. However, an array may reserve many positions that are unused, especially when most nodes have only a small number of children.

A sorted collection of child links is another possible choice. It can represent sparse children without allocating a full array, while requiring an ordered search among the available links.

These choices change implementation details, memory usage, and the practical cost of finding a child. They do not change the central algorithm:

1. Inspect the next character.
2. Determine whether the current node has a matching child.
3. Follow that child if it exists.
4. Create it during insertion if it does not exist.

The right representation depends on the character set and the constraints of the application. A basic Trie does not require one universal child-storage strategy.

A second complete example​

Consider inserting these words:

to
tea
ten
in
inn

After inserting to, the Trie contains:

root → t → o  [word: to]

When tea is inserted, the t node is reused. Since it does not have an e child, create one, then add a below it and mark a as terminal.

When ten is inserted, the path t → e is reused. Add an n child below e and mark it as terminal.

When in is inserted, create a separate i branch at the root, then add n and mark it as terminal.

When inn is inserted, the path for in already exists. Add another n below the existing terminal n, and mark the new node as terminal.

The conceptual result is:

root
├── t
│   ├── o  [word: to]
│   └── e
│       ├── a  [word: tea]
│       └── n  [word: ten]
└── i
    └── n  [word: in]
        └── n  [word: inn]

This example demonstrates several important cases:

• tea and ten share the prefix te.
• in is a complete word and also a prefix of inn.
• A terminal node does not have to be a leaf.
• Words can share a short prefix even if they later diverge completely.

A prefix lookup for te reaches the e node below t. Its subtree contains tea and ten. An exact search for in reaches a terminal node, so in exists as a complete word. That same node has a child, so inn is also available as a longer completion.

Duplicate insertion​

If the same word is inserted more than once, the insertion process follows the same existing path. The final node is marked as a word again, but no duplicate nodes are needed.

For example, inserting car twice does not create a second c → a → r path. The Trie represents the word's character sequence once.

A basic Trie therefore behaves naturally like a set of strings with respect to membership. If an application needs additional information, such as a frequency or a count of duplicate insertions, that information can be stored separately at the terminal node. Such metadata is an application-specific extension; it is not required for the basic prefix-tree structure.

Common mistakes and how to avoid them​

Mistake 1: treating every existing path as a complete word​

A path may exist only because it is a prefix of a longer word. If the Trie contains card, an exact search for car must return false unless the r node is also marked as terminal.

Fix: always check the end-of-word marker after consuming the complete query.

Mistake 2: assuming terminal nodes are leaves​

A word can be a prefix of another word. car and card can coexist, so the node for car can be both terminal and connected to a child.

Fix: store terminal status independently from the child links.

Mistake 3: replacing an existing child during insertion​

If a node already has a child for the next character, that child represents a previously inserted shared prefix. Replacing it can disconnect existing words.

Fix: reuse the child when it exists; create a new child only when it is missing.

Mistake 4: exploring only one continuation​

A prefix can branch into many valid completions. For ca, following only the r branch would miss cat.

Fix: after reaching the prefix node, explore every relevant child unless the application intentionally limits the result set.

Mistake 5: losing the current word during traversal​

The traversal must reconstruct the full string associated with each terminal node. If it only knows the node but not the path used to reach it, it cannot produce the suggestion text.

Fix: carry the current text through recursion, or maintain a mutable path that adds a character when entering a branch and removes it when leaving.

Mistake 6: ignoring a missing prefix character​

If a required child is absent, no word below another branch can match the query. Continuing the search elsewhere cannot produce a valid completion.

Fix: stop immediately and return an empty result when the prefix path does not exist.

Mistake 7: forgetting the empty-result case​

Autocomplete must handle prefixes that do not appear in the Trie at all. A missing first character and a missing character later in the path both mean that there are no matching stored words.

Fix: define the missing-path behavior explicitly, usually as an empty list of suggestions.

Practical autocomplete behavior​

The basic Trie explains how to find all matching words, but an actual search box may need additional rules for how suggestions are presented.

For example, an interface may want only a limited number of results. The traversal can stop after enough suggestions have been collected. This avoids returning more results than the interface needs, although the exact amount of work depends on the traversal order and on where acceptable suggestions are found.

The order of child traversal also affects the order in which suggestions are discovered. If children are visited in a consistent character order, the results can appear in a predictable lexical-style order. If children are stored in an unordered mapping, the traversal order may depend on the mapping's representation. This changes presentation order, not the set of words that match the prefix.

Applications may also associate additional information with complete words. For example, a terminal node or a related record could contain information used by the application when choosing among multiple completions. The basic structure still performs the same first step: locate the prefix node and then examine the words reachable below it.

Input normalization is another practical concern. Inserted strings and queries should follow a consistent interpretation of characters. If one side treats uppercase and lowercase letters differently while the other side does not, strings that appear equivalent to a user may follow different paths. The Trie does not decide this policy; the surrounding application should apply the same normalization rules when building and querying it.

When a Trie is a good fit​

A Trie is a natural choice when the important operations involve strings and prefixes, including:

• inserting words or identifiers character by character,
• checking whether a complete word exists,
• checking whether any stored word begins with a prefix,
• locating the subtree associated with a typed prefix, and
• collecting possible completions from that subtree.

The structure is especially intuitive when an application repeatedly moves from a prefix to its possible continuations. The prefix is not merely a value to compare against every stored word; it identifies a specific node and therefore a specific region of the structure.

A Trie may be less attractive when the data does not have a meaningful character-by-character prefix relationship, when memory usage is the dominant concern, or when the only required operation is exact membership and another representation is simpler for that purpose.

A data structure should be selected according to the operations the application performs. A Trie is powerful for prefix-oriented work, but that does not make it the best representation for every collection of strings.

A practical implementation plan​

When implementing a basic Trie, define the node contract first:

TrieNode:
    children: links from characters to child nodes
    isWord: whether a complete word ends at this node

Then build the functionality in small steps:

1. Create a root node representing the empty prefix.
2. Implement insertion by creating or reusing one child per character.
3. Mark the final node after the whole word has been processed.
4. Implement exact search with a final isWord check.
5. Implement prefix lookup by returning the node reached after the prefix.
6. Implement descendant traversal to collect complete words.

Test the boundary cases deliberately:

• an empty Trie,
• a query whose first character is absent,
• a query whose middle character is absent,
• a prefix that is not itself a complete word,
• a word that is also a prefix of another word,
• duplicate insertion, and
• a prefix that branches into several completions.

These cases test the most important distinctions in the structure: a path is not automatically a word, a terminal node is not necessarily a leaf, and autocomplete must consider all relevant branches.

The simplest mental model​

The easiest way to remember a Trie is to imagine walking through a collection of words one character at a time.

• The root means that no characters have been chosen.
• Following an edge labeled c means the current prefix now ends in c.
• Following an edge labeled a after that changes the prefix to ca.
• Reaching an end marker means that the current path spells a complete stored word.
• Looking below a prefix node means asking which longer words begin with that prefix.

With this mental model, insertion and lookup are nearly identical walks. Insertion creates missing steps. Exact search checks that every step exists and then checks whether the final position is terminal. Autocomplete follows the typed steps and then explores the available continuations.

Final takeaways​

A Trie is a prefix tree built from shared character paths. Words with common beginnings reuse the same nodes, and words branch only when their characters diverge. This shared structure makes prefixes explicit rather than requiring them to be rediscovered by comparing the prefix with every complete string.

Building a Trie means walking each word from the root, creating missing character links, reusing existing links, and marking the final node. Exact-word search follows a complete query and checks the end-of-word marker. Prefix lookup follows the typed characters and returns the node representing that prefix. Autocomplete then explores the subtree below that node and reports each complete word it encounters.

The central algorithmic insight is simple:

In a Trie, a prefix identifies a precise location in the data structure.

Once that location is found, the possible completions are the complete words reachable below it. That is why a Trie provides such a natural model for the behavior of a search box that seems to know what you are typing.