What Is a Trie? Prefix Tree Data Structure Explained

A trie (pronounced “try,” short for retrieval tree, and also called a prefix tree) is a tree data structure that stores strings by sharing common prefixes across branches. Instead of storing each word as a whole unit, a trie breaks words into characters and merges the paths for any words that share a beginning — “car,” “card,” and “care” all share the same first three nodes before branching apart. That structure makes prefix-based operations, like autocomplete, fast in a way that other data structures don’t naturally support.

How the structure works

Each node in a trie represents a single character, and the path from the root to a given node spells out a prefix. A node has one child per possible next character, plus a marker indicating whether the path to that node completes a full word (since “car” might be both a complete word and a prefix of “card”). The root itself represents the empty string.

Inserting a word means walking from the root, following or creating a child node for each character in turn, and marking the final node as the end of a word. Searching for a word follows the same path and checks whether the final node is marked complete. Searching for a prefix is nearly identical, just without requiring that final “complete word” marker — you only need to confirm the path exists.

Why prefix operations are fast

The structural trick is that a lookup only ever depends on the length of the string being searched, not on how many other strings are stored in the trie. Searching for a word of length k means following exactly k edges, regardless of whether the trie holds a hundred words or a million — a property described in Big O notation as O(k) time, independent of the total number of stored entries. Finding every word with a given prefix is just as direct: walk to the node representing that prefix, then explore everything beneath it, since every word sharing that prefix necessarily lives in that subtree.

Common uses

• Autocomplete and search suggestions — typing a few characters and getting a ranked list of completions is a direct application of walking to a prefix node and collecting the words beneath it.
• Spell checkers — checking whether a word exists, and suggesting corrections by exploring nearby paths in the tree, both map naturally onto trie traversal.
• IP routing tables — routers use a trie-like structure over binary IP prefixes to perform longest-prefix matching, picking the most specific matching route for a packet’s destination.
• Dictionary and word-game implementations — validating whether a sequence of letters forms a real word, or enumerating all valid words reachable from a set of tiles, both lean on prefix traversal.

Trie vs hash table vs binary search tree

	Trie	Hash table	Binary search tree
Exact lookup	O(k), k = string length	O(1) average	O(log n) average
Prefix search	Native and fast	Not supported directly	Requires extra logic, less natural
Sorted iteration	Yes, via traversal	No	Yes
Memory overhead	Can be high (a node per character)	Lower per entry	Moderate
Best fit	Prefix-heavy workloads (autocomplete, routing)	Fast exact-match lookups	Ordered data with range queries

A hash table beats a trie for plain “does this exact string exist” checks — it’s typically faster and simpler. A trie earns its keep specifically when prefixes matter, which a hash table has no natural way to support: hashing “car” and hashing “card” produce unrelated results, so there’s no way to find “everything starting with car” without scanning every entry.

The tradeoff: memory

A trie’s biggest weakness is memory. In the naive implementation, every node holds a slot for every possible next character, and most of those slots go unused for any given branch — a node representing a single letter might have room for dozens of possible children but only one or two in actual use. Real implementations mitigate this with compressed variants that merge chains of single-child nodes into one edge, or with more compact child representations, but the basic structure trades memory for the speed of prefix operations. Whether that trade is worth it depends on whether prefix lookups are actually central to what you’re building — the same kind of cost-benefit judgment behind choosing a bloom filter over an exact-membership structure when approximate answers are good enough.

The takeaway

A trie stores strings character by character, sharing common prefixes across branches so that a lookup costs time proportional only to the string’s length, and prefix searches are a direct traversal rather than a scan. It’s the natural fit for autocomplete, spell-checking, and prefix-based routing — anywhere “what starts with this” matters as much as “does this exact thing exist.” For plain exact-match lookups without a prefix requirement, a hash table is usually the simpler and cheaper choice.