DataslopeTries
Learn prefix trees, trie operations, memory trade-offs, and prefix-query challenges in C++
A trie, or prefix tree, stores strings by sharing common prefixes. Each node represents a prefix. Edges represent characters, and a boolean flag marks whether the prefix is a complete word.
Trie shape
This trie contains cat, car, cart, and dog.
Compared with std::unordered_set<std::string>, a trie often uses more memory because every node stores child links. In exchange, prefix queries are fast and natural.
Length-based complexity
Trie insert, exact search, and prefix search are O(L), where L is the length of the key, independent of how many other words are stored.
Node representation
For lowercase English letters, std::array<TrieNode*, 26> is compact and fast. For arbitrary characters, std::unordered_map<char, TrieNode*> is flexible.
Full implementation with unordered_map
This version is easy to read and works for any character.
Insert
Insertion creates missing nodes along the word path, then marks the final node as a complete word.
Search vs prefix search
Exact search requires the final node to have isWord = true. Prefix search only needs the path to exist.
Autocomplete by DFS
Once you walk to a prefix node, collect all words below that node.
Use cases
Tries are useful for autocomplete, spellcheck, IP routing, longest-prefix matching, and dictionary-word search on a board.
Practice: Implement a Trie
Complete the Trie class with insert, search, and startsWith.
Practice: Count words starting with prefix
Build a trie from the words and return how many inserted words start with the given prefix.
Practice: Longest common prefix
Build a trie and walk while there is exactly one child and the current node is not the end of a word.
Check your understanding
What is the time complexity of searching for a word of length L in a trie?
O(1) always
O(L)
O(n log n)
O(26 to the power L)
When can a trie beat a hash set of strings?
When many prefix queries such as starts-with or autocomplete are needed.
When memory must always be minimized.
When only exact membership is needed and no prefixes matter.
When strings cannot share prefixes.
What does a node in a trie represent?
A whole independent hash table of all words
A prefix formed by the path from the root to that node
Always exactly one complete word
The sorted rank of a string