What do we do to get constant time lookup into any data? No free lunches in computer science i'm afraid. We have to sacrifice something, in case of Tries we gain constant speed by sacrificing memory.
For some applications this is worth it. Sometimes, it isn't. After you learn more about how it works under the hood, you'll be more prepared to decide on these sorts of trade-offs.
Interviewers at FAANG companies often test people on this knowledge in order to find the engineers with the biggest toolbox.
Tries consume so much memory because every single node, an associative array pointing at another Trie node (or nothing). If you want to have a block in the array for every piece of alphabet, common for use-cases like autocomplete. Each of your nodes needs to have an array of 26 inside of it.
Associative arrays are sometimes implemented with a hashmap -If you want to learn in-depth what hashmaps check our article explaining it in depth
Here is how a single node of a Trie looks like
You might be a little bit intimidated in the beginning with how complex they look, but trust me, here is where good metaphor goes a long way here.
You can think of a Trie as a room with a set of doors.
Some of them are opened. Some of them are not.
Lets say you want to check if "bar" is a valid word in our Trie tree.
You go into the root room of our Trie, check if door['b'] is open, if so go through it, into a identical with the same amount of doors. You check if door['a'] is open. If its not, you can immediately conclude "bar" is not present without checking further. This quality of Tries makes them a great pick for spellcheckers and autocomplete.
Lets say now you want to check if "orange" is a valid word.
You go back to the root, check if door['o'] is open you go through the door then door['r'] , door['a'], door['n'], door['g'], door['e'] After you enter the final room that door labeled 'e' got you. You can see valid word spray painted on a wall. Now we know 'orange' is in our Trie tree.
function valid_string(string, node) if !node: node = trie_root_node // if no node is supplied then go from root else: if string = "" and node.valid_word == True: return True //if the string is empty and this node valid current_character = string // checking first character else if node['current_character'] != null: // door is open! node = node['current_character'] // go through the door string = string[1:] // remove first character, we already checked valid_string(string, node) // call function recursively else: return False // the string was not a word
Now we know value of valid_string("orange") is True. Which means its a valid word in our Trie tree.
Using the same principle we can add values to the try, by opening doors and building a new room behind them, one by one, and placing the value in the last one.
Tries are truly magical allowing us constant time search but by sacrificing a lot of memory.
Autocomplete is done with tries?
By adding a branch weight (thickness) inside of the pointer array. Creating something like an auto-complete that can learn from input.
Whats my next letter? Go over all 27 of there and check the most weighted one
Keep doing that until you find one with value. Voila you found probably what your user wants to type.
Is there a way to use less memory for a Trie?
If you want to save memory on the Trie tree the first place to cut would be the size of the array. But this would mean possible collisions
In this case we can avoid collisions by pointing the values to a linked list of values instead. We would sacrifice some lookup speed, but reduce the memory consumption.
Of course you can design your associative array in such a way, that collisions it will be impossible. Or astronomically unlikely like using a checksum algorithm, giving us trillions or even quadrillions possible combinations based on the algorithm used. All while using 36 "doors" per Trie node (a-z 0-9).
Hopefully your mind is now flowing with possibilities how to solve all interview problems in a way not many other candidates do. A faster, better way.
Comment below if you would like a more-in-depth article about tries with code examples and in depth exploration of different Trie structures.