Trie

What is a Trie data structure?

If you know what a Tree data structure is, you can think of a Trie as an ordered tree, such that it is similar to a Binary Search Tree but it it not necessary to have both key and value given a node of the tree. The node has a value if and only if it has a valid key.

Let's look at an example.

Trie is especially powerful and commonly used when dealing with letters and words.


The above is a trie example from Wikipedia that uses words as key and integer as value.

It takes string as an input and outputs an integer value if there is a match. So trie_example.get("tea") will return an integer 3, and trie_example.get("te") will return null since there is no value associated with that node. "tea" is considered a valid key while "te" is not, since we define the key is valid if it is a valid English word.

This kind of trie can be very powerful in time complexity when dealing with words, but it also uses a lot of space especially when there are lengthy words. A space-optimized trie called Radix tree can be used to solve this problem. Use word matching as an example, radix tree will not only store one letter in each node but as many as its children they share.