What is a prefix tree?

A prefix tree is also known as a Trie; it is used to optimize the search complexities. If we search keys or words in a Binary Search Tree (BST) then the time complexity could go up to O (M * log N) whereas M is length of the words inserted and N is the total number of words inserted in the tree. However, when the prefix tree is used the search time complexity is reduced to O(M).

How are prefix trees created?

Different words are mapped on a prefix tree. The tree takes a string as a parameter and then creates a new node for each character of that string/word. The node registered for the last character of the string/word is marked as the end of word. A Boolean variable is usually used to do this.

The illustration below explains how a prefix tree is created:

Why is it called a prefix tree?

As you’ve seen in the slides above, a prefix tree uses prefixes while inserting words in the tree. For example, if the word “DON” was already inserted in the tree and another word, “DO”, is passed as an input; then, the Prefix tree would use the prefix “DO”,of the word “DON”, to examine that the word “DO” is already present in the tree.

Another example could be if the word “Education” is already present in the tree and another word,“Educative”, is inserted. The prefix tree will use the prefix “EDUCATI” ,of the word “EDUCATION”, and create a node for the character “V”(as a child of “I”) and another node for the character “E” (as a child of “V”).