A trie is a tree-based data structure used to store strings by sharing common prefixes. This cheat sheet helps students understand how tries organize words, support fast lookup, and compare with hash tables and binary search trees. It is useful for spelling tools, autocomplete, dictionaries, routing tables, and word games.
Students in grades 11-12 can use it as a quick reference for algorithms, diagrams, and complexity analysis.
The most important trie ideas are nodes, edges labeled by characters, the root, child links, and end-of-word markers. Insert, search, and prefix lookup process one character at a time from left to right. If a word has length L, the main operations usually take O(L) time, independent of how many words are stored.
Space depends on the number of nodes created, which is affected by how much prefix sharing the stored strings have.
Key Facts
- A trie stores strings in paths from the root, where each edge or child link represents the next character in a key.
- Each node usually stores a map or array of children and a Boolean flag such as isEndOfWord to mark a complete stored word.
- To insert a word of length L, follow or create one node per character, then set isEndOfWord = true at the final node.
- To search for a complete word of length L, follow each character and return true only if the final node exists and isEndOfWord = true.
- To test whether any stored word starts with a prefix of length P, follow the prefix characters and return true if the final prefix node exists.
- Trie insert, search, and prefix lookup are O(L) time for a word of length L, assuming child lookup is O(1) on average.
- Trie space complexity is O(total characters stored) in the worst case, but shared prefixes can reduce the number of nodes.
- Using an array of size A for children gives O(1) child access but may waste space, while using a hash map saves space for sparse alphabets.
Vocabulary
- Trie
- A tree data structure that stores strings by sharing common prefixes along paths from a root node.
- Root
- The starting node of a trie, usually representing the empty string before any characters are read.
- Child link
- A connection from one trie node to another that represents the next character in a stored string.
- End-of-word marker
- A Boolean flag on a node that shows a complete word ends at that node.
- Prefix lookup
- An operation that checks whether any stored word begins with a given sequence of characters.
- Alphabet size
- The number of possible characters that can appear at each position, often represented as A in trie analysis.
Common Mistakes to Avoid
- Forgetting to set isEndOfWord after insertion is wrong because the trie may contain the path but not recognize the complete word.
- Returning true for a word search just because the path exists is wrong because that path may only be a prefix of a longer word.
- Deleting nodes without checking whether they are shared is wrong because removing a shared prefix can destroy other stored words.
- Claiming trie search is O(n) where n is the number of stored words is wrong because search depends mainly on the query length L.
- Using a large fixed child array for every node without considering alphabet size is wrong because it can waste a large amount of memory.
Practice Questions
- 1 Insert the words cat, car, cart, and dog into a trie. How many nodes are needed if the root counts as one node?
- 2 A trie stores 10,000 words. If a searched word has length 8 and child lookup is O(1) on average, what is the search time in Big O notation?
- 3 A lowercase English trie uses a fixed array of 26 child pointers per node and contains 2,000 nodes. How many child pointer slots are allocated in total?
- 4 Explain why a trie can answer prefix queries efficiently, and describe one situation where it might use more memory than a hash table.
Understanding Trie Data Structure Reference
A terminal marker solves an important ambiguity. Suppose the structure contains the words car and cart. Both words travel through the same first three letters.
The node reached after car must say that a complete word ends there, even though it has a child for t. Without that marker, a search for car could mistakenly fail because the path continues. The same issue appears when one key is a prefix of another, such as in, into, and inside.
When drawing a trie, label terminal nodes clearly. It helps separate the idea of a valid stored word from the idea of a path that merely exists.
Deletion needs more care than insertion. To remove cart, first follow its path and clear the terminal marker at its final node. Then inspect the path from the end back toward the root.
A node can be removed only when it has no children and does not mark another complete word. In the car and cart example, removing cart may remove the t node, but the car node must remain because car is still stored.
If car is removed while cart remains, its terminal marker is cleared but its nodes stay. This backward cleanup prevents broken paths and avoids leaving unnecessary nodes.
The claimed running time depends on the cost of finding a child. A fixed array works well when the allowed character set is small and known, such as lowercase English letters. Each character can be converted to an array position quickly.
However, every node reserves room for every possible character, even when most positions are empty. A map stores only children that actually occur, which can save much memory for varied text. Its lookup cost may be average constant time with hashing, though real performance includes hash work and memory overhead.
A sorted child list uses less space in some cases, but locating a child can take longer. Students should state the chosen child representation before making a complexity claim.
Real text needs rules before it enters the trie. A search system may convert letters to lowercase so that Cat and cat match. It may remove punctuation, keep apostrophes, or treat accented letters as distinct.
These choices change which paths exist. Autocomplete begins by finding the node for the typed prefix, then visits descendant paths to produce possible completions. The prefix search itself is fast, but listing many suggestions takes time because each result must be read and returned.
Large systems may store a frequency count or a list of top suggestions at nodes so common completions appear first. Tries can use substantial memory when keys share few beginnings.
Compressed tries reduce this cost by storing a whole substring on one edge when no branching occurs. This preserves prefix structure while reducing the number of separate nodes.