Monthly Archives: May 2015


Trie or prefix tree is a tree-like data structure that implements dictionary abstract data type. In other words, trie allows to store key/value pairs in hierarchical structure. For example, let say we have words {a, as, air, aim, ail, car, i, milk, be, bag}. These words can be represented as follows.


As you can see the root of the trie is an empty string that has five direct children. Every child represents first letter of a given word so that the words with the same prefix share the common nodes. As a result, a key can consist of one or more nodes, but values stored in one node.

Continue reading Trie