Trie Delete Operation

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
14 upvotes
Asked in company
MAQ Software

Problem statement

You are given a Trie data structure which stores words or strings and a string 'WORD'. Your task is to perform the delete operation on the Trie to delete an input string 'WORD' from it.

You have to complete the function deleteWord() which takes the root of input Trie 'ROOT' and a string 'WORD' as parameters and returns a TrieNode pointer. If the string 'WORD' exists in the trie, it must be deleted, and the root of new Trie should be returned. If the correct word is deleted, the output will be “TRUE” else it will be “FALSE”.

If the string “word” doesn’t exist in the Trie, then no delete operation will take place, and the output will be “TRUE”. If for any query, the output is “FALSE”, then the answer is wrong.

Trie is a data structure which is like a tree data structure in its organization. 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 Hashmaps, Trees etc. in time complexities of its operations.

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 which mark the ending of a word in the Trie.

To define this problem, we perform operations with the following two types of queries.

To insert a string WORD in the Trie, we use ‘’Type 1’’ query.

Example: 1 WORD 

We will put the integer 1 before the input string WORD to insert it into the Trie.

To delete the string  WORD from the Trie, we use the “Type 2” query.

Example: 2 WORD

We will put integer 2 before the input string WORD to delete the string WORD from the Trie.

Example:-

Query A - 1 coding
This query will add the string “coding” in the trie.

Query B - 2 coding
This query will delete the string “coding” from the Trie. After deleting the string, it will produce “TRUE” as it’s output.

Note:

If anywhere in the output, the word “FALSE” is printed, it means that the given string is not deleted successfully from the Trie, and hence it will lead to a Wrong Answer.
Detailed explanation ( Input/output format, Notes, Images )

Input Format

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

The first and the only line of each query contains an integer ‘T’ denoting the type of query and a string 'WORD' denoting the query string both separated by a single space

Output Format:

For each query of Type 2 print "TRUE" if the string WORD is deleted from the Trie or "FALSE" if it is not deleted.

Note:

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= 'Q' <= 10000
1 <= 'T' <= 2
1 <= |WORD| <= 20

Where |WORD| is the length of the input string
Each input string 'WORD' will consist of lower case alphabets (a-z) only.

Time limit: 1 second
Sample Input 1 :
5
1 coding
1 ninjas
2 coding
2 code
2 ninjas
Sample Output 1 :
TRUE
TRUE 
TRUE
Explanation to Sample Input 1 :
Query 1: "coding" is inserted in the Trie
Query 2: "ninjas" is inserted in the Trie
Query 3: "TRUE" is printed as "coding" is deleted from the Trie
Query 4: "TRUE" is printed as "code" is not present in the Trie
Query 5: "TRUE" is printed as "ninjas" is deleted from the Trie
Sample Input 2 :
10
1 facebook
1 google
1 amazon
2 facebook
1 face
2 google
2 face
2 amaze
1 apple
2 amazon
Sample Output 2 :
TRUE
TRUE
TRUE
TRUE
TRUE
Hint

Can we do it with the help of recursion in the bottom-up approach?

Approaches (1)
Implementation

We are given a function deleteWord which takes the root node of input Trie ROOT and a string WORD as parameters.

  1. In the function void deleteWord ( TrieNode* root, string word ):
    1. Define a variable DEPTH = 0, which will mark each character of the string WORD in our recursive program.
    2. Now create TrieNode* deleteWordHelper() function which the root node of input Trie ROOT, a string WORD, and an integer DEPTH as its parameters. This is also the definition of our recursive function deleteWordHelper().
    3. We update our current root with the result of our recursive function. root = TrieNode*deleteWordHelper( root, word, depth)
    4. Also, create a bool isEmpty() function, which takes input Trie node root as the only parameter and returns whether the Trie is empty or not. This function would be helpful in finding whether the current word is a prefix to another long word or not.
  2. In the function TrieNode* deleteWordHelper():
    1. We define our base condition, which is when the trie is empty, or “ROOT == NULL”. In that case, we return our function.
    2.  We process the last character of the string WORD by checking if DEPTH == WORD.size()
      1. After the removal of the given string WORD, the current node will not be the end of the word, so we do “root->isEnd = false”
      2. Now if the current node is not the prefix of any other word, we delete the current node and return the root as NULL.
    3. If the current node is not the last character of the string WORD, we use recursion to find it by recurring for the child obtained using ASCII value.
    4. If the current node does not have any child and is also not the end of any other word, we delete it and return node as NULL.
Time Complexity

O(N*W) where N is the number of queries and W is the average length of the input string.

 

As clearly visible, we are iterating over the string “word” and checking in the array for the next character of the word and finally deleting so Overall Time Complexity for insert and search function is O(W).

Space Complexity

O(N*W) where N is the number of words inserted through insert queries and W is the average length of the input string.

 

As before deleting the words from the trie, the program is also inserting those words. So space can be at max 26*N*W and hence the space complexity is O(N*W).

Code Solution
(100% EXP penalty)
Trie Delete Operation
Full screen
Console