Solution: Implement Trie (Prefix Tree)

Statement

Trie is a tree-like data structure used to store strings. The tries are also called prefix trees because they provide very efficient prefix-matching operations. Implement a trie data structure with three functions that perform the following tasks:

• Insert (word): This inserts a word into the trie.
• Search (word): This searches the given word in the trie and returns TRUE, if found. Otherwise, return FALSE.
• Search prefix (prefix): This searches the given prefix in the trie and returns TRUE, if found. Otherwise, return FALSE.

Constraints:

• $1 \leq$ word.length, prefix.length $\leq 500$
• The strings consist only of lowercase English letters.
• At most, $10^3$ calls in total will be made to the functions.

Pattern: Trie

There are multiple data structures that can be used to store strings. However, for a majority of them, searching a string requires a complete traversal of the stored data. A more efficient approach is to use a trie.

A trie is a tree of characters. The trie takes a word as a parameter and creates a new node for each character of that word. This way, the given string is searched character by character and does not require an exhaustive search. Therefore, this problem fits perfectly in the trie pattern.

Solution

To implement a Trie class, we’ll initialize the root node of the tree in the constructor. This node will be of the Node type. The Node class contains a dictionary of nodes and a boolean variable, which determines if the character is at the end of a word.

Let’s discuss the following functions now:

• Insert(word): In this function, we take a word as input. We begin from the root node and iterate over the string one character at a time. At each node, we check whether or not a child node with the character is present. If it’s not present, a new node is initialized. For the last character of the word, we also set the boolean variable to TRUE for the corresponding node.

• Search(word): In this function, we start traversing from the root node and check if the first character is the child of the root node. If so, we move on to that node and check its children for the next character. If, at any point, we do not find the node corresponding to a character, we return FALSE. Alternatively, we return FALSE when we find the whole word, but the boolean variable is not TRUE for the last node, signaling that the word doesn’t end here. We only return TRUE when all the characters match, and the word ends at that point.

• Search prefix(prefix): This function is mostly the same as the search function. The only exception is that we do not check if the boolean variable is also set to TRUE in the last-found node because we aren’t looking for a complete word but just a prefix. In the trie above, for instance, SearchPrefix("by") should return TRUE.