Last Updated: 30 Dec, 2020

Trie Implementation

Moderate

Asked in companies

Solve now

Problem statement

Implement a Trie Data Structure which supports the following three operations:

Operation 1 - insert(word) - To insert a string WORD in the Trie.

Operation 2-  search(word) - To check if a string WORD is present in Trie or not.

Operation 3-  startsWith(word) - To check if there is a string that has the prefix WORD.

Trie is a data structure that is like a tree data structure in its organisation. It consists of nodes that store letters or alphabets of words, which can be added, retrieved, and deleted from the trie in a very efficient way.

In other words, Trie is an information retrieval data structure, which can beat naive data structures like Hashmap, Tree, etc in the time complexities of its operations.

The above figure is the representation of a Trie. New words that are added are inserted as the children of the root node. 

Alphabets are added in the top to bottom fashion in parent to children hierarchy. Alphabets that are highlighted with blue circles are the end nodes that mark the ending of a word in the Trie.

For Example:-

Type = ["insert", "search"], Query = ["coding", "coding].
We return ["null", "true"] as coding is present in the trie after 1st operation.

Input Format

The first input line contains an integer 'Q' representing the number of queries.

The next line contains an array that defines the type of the query.

The next line contains the words on which we have to perform operations.

Output Format:

The only line contains an array that contains the answer to the query that is "true" or "false" for 2nd and 3rd type of operation and "null" for 1st operation.

Solve now

Approaches

01 Approach

We are given two functions, insert and search, both taking a single string as the only parameter.

In the function void insert ( string word ):
1. Initialize a “TEMP” node with the root node of Trie.
2. Iterate over the string “WORD” from left to right and if there is no node present for the next character of the string then create a new node and store it in the child member of the previous character’s node.
3. Keep updating the current node to the corresponding node for the next character of the word.
4. Finally, when we reach the end of the word, mark the isEnd member of the current node to true as it will denote if the word is present or not.
In the function void search ( string word ):
1. Initialize a “TEMP” node with the root node of Trie.
2. Iterate over the string “WORD” from left to right and if there is no node present for the next character of the word then return false as the word is not present in the Trie.
3. Keep updating the current node to the corresponding node for the next character of the word.
4. Finally, when we reach the end of the word, return the isEnd bool variable of the current node as it will denote if the word is present or not.

Solve now