Trie tree

Until now, we have seen different types of trees, such as binary trees, binary search trees, red-black trees, and AVL trees. In all these types of tree, the content of a node (a value or a key) is not related to the content of a previous node. A single node has a complete meaning, such as a value or number by itself.

But in some scenarios in real life, we need to store a series of data in which those values have common parts; think of it as the suffixes or prefixes in related words, in the alphabet, in a telephone directory.

Here is where a trie tree shines. They are ordered data structures where edges contain part of a key and its descendant nodes have common share part of the previous values. Check this example out:

Trie tree example – storing the words plan, play, poll, post

As you can see in the previous figure, each edge of the tree contains part of a key, and by adding every edge key from the top to a specific node (or leaf), we can build a complete key.

Some implementations...