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.