toolkit

Trie / Autocomplete Simulator

Runs in browser

Visualize how Trie data structure enables fast prefix search

Dictionary (11 words)

apple
app
application
apply
banana
band
bandana
cat
car
card
care

Statistics

Nodes
30
Search Time
0.000ms

How to Use

Type a prefix to search the Trie.

You will see:

  • Highlighted Path (Root → Match)
  • Filtered Search Results
  • Node Count & Search Time
Search Results

Results (0)

Type a prefix to search...

Trie Structure

Highlighted path: none
Root
└─ a → p → p → l → e
└─ a → p → p
└─ a → p → p → l → i → c → a → t → i → o → n
└─ a → p → p → l → y
└─ b → a → n → a → n → a
... and 6 more

Related Tools

Dev

Regex Tester

Data Tools

Text Diff

Simulators

Vector Embedding

The Definitive Guide to Tries (Prefix Trees)

A Trie (pronounced "try", derived from retrieval) is a specialized tree data structure used for the highly efficient storage and retrieval of strings. Unlike binary search trees or hash tables, it excels at prefix-matching operations, making it the undisputed champion data structure for Autocomplete systems, spell checkers, and IP routing.

Architecture & Mechanics

In a standard tree, a node stores an entire key. In a Trie, a node represents a single character of the key. The path from the root down to a given node spells out the prefix or the complete word.

The Nodes

Each node typically contains a Hash Map (or fixed-size array) pointing to its children, and a boolean flag isEnd indicating whether this exact node marks the completion of a valid inserted dictionary word.

Prefix Sharing

The true magic of the Trie is memory deduplication via prefix sharing. The words "app", "apple", "application", and "apply" will all reuse the exact same memory path for 'a'-'p'-'p'.

Time Complexity Breakdown

Tries are blindingly fast because their performance is fundamentally decoupled from the total number of items stored in the dictionary.

Operation Trie O(L) Hash Table Binary Search Tree
Exact Search O(L) O(1) O(L * log N)
Prefix Search O(L) O(N) - Must scan all O(L * log N)
Insertion O(L) O(L) O(L * log N)
L = Length of the word/query | N = Number of total words in dictionary

*Note: While Hash Tables beat Tries at Exact Search O(1) vs O(L), a Hash Table is entirely useless if the user has only typed "ap" and you need to fetch all valid continuations.

Production System Design: Google Search Autocomplete

A basic Trie returns all matching words. But when you type "new" into Google, it cannot return 500 million matches. It needs to return the Top 10 highest-frequency matches in less than 50 milliseconds.

The Cached Top-K Strategy:

Instead of just storing the character, each node in the Trie is modified to store a pre-computed array of its top 10 most popular children.

{ char: 'w', isEnd: false, // Cached list of the Top 5 results that exist recursively under this node topKCache: [ { word: "new york times", score: 9.8 }, { word: "new york", score: 9.5 }, { word: "new balance", score: 8.2 }, { word: "news", score: 7.9 }, { word: "new england patriots", score: 6.4 } ], children: { ... } }

When the user reaches node 'w', the API instantly returns the topKCache in O(L) time without needing to traverse the millions of sub-nodes below it via a heavy DFS algorithm. A background MapReduce job updates these caches offline periodically.

Real-World Use Cases

1. IDE Code Completion

When you type document.getE, standard IDEs use AST parsers combined with Tries to suggest getElementById nearly instantly.

2. Network Routing (CIDR)

The backbone of the internet uses a specialized binary Trie (Radix Tree/Patricia Trie). When an IP packet arrives, the router uses "Longest Prefix Match" against the Trie to figure out which port to forward it to.

3. Profanity Filtering

Chat applications use Aho-Corasick (an algorithm built on top of a Trie) to scan long incoming text messages for thousands of banned words simultaneously in a single O(N) pass.

4. Spell Checking

Used to check validity. When a word is not found in the Trie, an algorithm like Levenshtein distance traverses the Trie branching paths to find the closest valid dictionary words to suggest corrections.

Further Reading