Binary search trees are not the only way to organize data in a tree structure. In general, trees can have more than two child nodes, and the children can have other relationships to the parent node. One such alternate type of tree is the trie data structure.
What is a Trie Data Structure?
The trie (pronounced "try", as in "There is no try -- only do") stores nodes differently than the trees you have seen so far. Each node in a trie only stores part of the data, specifically a partial prefix of a complete data item. Child nodes store larger prefixes of the data being stored until the full data item is stored in a terminal node. By following links from the parent node to the child nodes, the complete data item is revealed. Because of the way they store their data, tries are also called prefix trees.
Tries are often used to store strings, but they are not limited to that. In the case of strings, each node of the trie adds an individual character to the string. Links lead from one character to the next, with leaves or other specially marked terminal nodes holding the final completed word.
As always, an example is helpful. The image below shows a trie which is storing five different words:
![[images/Trie example.png]]
The trie starts with an empty root -- this allows the trie to words starting with all letters. In this case, the root has two children, representing words that begin with the letters f and m. From each of these prefixes, the words far, for, max, mob, and mom are stored by adding letters to the prefix of the parent node to make a new prefix until there are no more letters to add.
Why use a Trie
Tries are very good for storing data that share common prefixes, such as words, telephone numbers, IP addresses, and so on. Tries can allow efficient lookup of this related data while allowing new data to be added as well.
Use Cases for a Trie
Tries are often used to store data used by spell checkers -- a word can be quickly and easily verified against the words in a trie by following links from letter to letter. If the word ends when the trie is on a leaf or terminal node, then the word is spelled correctly -- otherwise, the word is flagged as misspelled. Tries are also used in internet routing, storing IP addresses in tries to determine optimal routing paths.
Benefits of a Trie
A trie can easily solve problems that are much more difficult with other data structures. The prefix matching of a trie allows programs to implement features such as predictive text look-ahead based on what the user is typing, a key feature in many word processing programs and IDEs.
Other Kinds of Tries
A memory-optimized trie called a radix tree can be built from a naively constructed trie. In a radix tree, nodes with only one child are combined with their child to reduce the number of nodes and speed searches in the trie.
Summary: Tries
Another variation on the tree structure is that the trie stores the prefixes of data in each node rather than the full data item. Tries are often used in spell checkers and internet routing algorithms.