Data Structures
Trie (Prefix Tree)
Difficulty: Intermediate
Type the letters a-p-p into a search box and the autocomplete dropdown produces apple, application, apply, and appoint before you finish the next keystroke. The data structure doing that work is a Trie (or prefix tree), where every stored...
Trie (Prefix Tree)
Type the letters a-p-p into a search box and the autocomplete dropdown produces apple, application, apply, and appoint before you finish the next keystroke. The data structure doing that work is a Trie (or prefix tree), where every stored word is a path from root to a marked node and every shared prefix is shared in memory exactly once.
This lesson covers the trie node layout (a children map plus an isEndOfWord flag), insert, search, and startsWith operations that all run in O(m) for a query of length m (independent of how many words the trie holds), and a delete that has to be careful not to break paths used by other words. You will also analyze the space behavior, including when a trie wins over a hash set (prefix queries, lexicographic enumeration) and when it loses (memory-tight workloads with no prefix structure to exploit).
In Hash Map (Dictionary) Basics, you used hashing to answer 'have I seen this exact key' in O(1); a trie answers a strictly richer question (any prefix lookup) by trading O(1) exact-match for O(m) traversal. Trees: Binary Tree Fundamentals introduced the recursive child-pointer pattern, and a trie generalizes it from two children per node to one child per alphabet symbol.
With a trie in your toolkit, the curriculum moves on to graph and hash extensions that solve a different family of problems built on the same node-and-edge thinking.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Describe the trie node structure (children map + isEndOfWord flag) and explain how words are stored as root-to-node paths.
Implement insert, search, and startsWith operations on a trie in both JavaScript and Python.
Implement delete on a trie while preserving shared prefixes used by other words.
Trace trie operations step by step and predict the tree shape after a sequence of inserts and deletes.
Analyze time and space complexity of trie operations and compare tries to hash-based alternatives.
Identify real-world applications of tries including autocomplete, spell checking, and IP routing.
Why This Matters
01
Tries are a frequent interview topic -- problems like 'implement autocomplete,' 'word search II,' and 'longest common prefix' all expect trie-based solutions that interviewers look for specifically.
02
Every search engine, phone keyboard, and IDE uses trie-like structures under the hood for instant prefix-based suggestions, so understanding them connects directly to real-world systems.
03
Tries exploit shared prefixes to store large dictionaries far more space-efficiently than storing each word independently, and they answer prefix queries in O(m) time -- something hash maps cannot do natively.
04
Building a trie develops your ability to work with tree structures that have variable-width branching (not just left/right), a skill that transfers to N-ary trees, file systems, and routing tables.
Key Terms
7 terms you'll encounter in this lesson
Trie
A tree-shaped data structure (also called a prefix tree) where each edge represents a character and each path from the root to a marked node spells a stored word. The name comes from 'retrieval.'
Prefix
The leading portion of a string. For example, 'app' is a prefix of 'apple'. In a trie, every ancestor of a node represents a prefix of all words stored below that node.
isEndOfWord
A boolean flag on a trie node indicating that the path from the root to this node represents a complete word in the dictionary, not just a prefix of a longer word.
Children Map
The mapping from characters to child trie nodes. In JavaScript this is typically a Map or plain object; in Python a dict. It can also be a fixed-size array of length 26 for lowercase English letters.
Prefix Search (startsWith)
An operation that checks whether any stored word begins with a given prefix. It traverses the trie character by character and returns true if all characters are found, regardless of the isEndOfWord flag.
Autocomplete
A feature that suggests complete words as a user types a prefix. Implemented on a trie by traversing to the prefix node and then collecting all words in the subtree below it.
Longest Prefix Match
Finding the longest stored prefix that matches a given input. Used in IP routing tables where the longest matching network prefix determines packet forwarding. Tries solve this in O(m) time.
Heads Up
Common misconceptions to watch out for
"A trie is just a binary tree with characters"
Unlike a binary tree, each trie node can have up to 26 children (for lowercase English) or even more for Unicode. The branching factor is the alphabet size, not 2. This is what makes tries an N-ary tree.
"If a node exists in the trie, it represents a stored word"
A node only represents a complete word if its isEndOfWord flag is true. The node for 'a-p-p' exists when 'apple' is stored, but 'app' is not a word unless isEndOfWord is set at that node.
"Deleting a word means deleting all its nodes"
You can only remove nodes that are not shared by other words. Deleting 'apple' from a trie that also contains 'app' just clears the isEndOfWord flag on the 'e' node and removes unshared trailing nodes. The nodes for 'a', 'p', 'p' must stay because 'app' still needs them.
"A hash set is always better than a trie for word lookup"
Hash sets can check exact membership in O(1) average, but they cannot answer prefix queries like 'find all words starting with pre-' without scanning every key. Tries handle prefix queries in O(m + k) where k is the number of matches.