Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction to tries 
2.
Working of the Code for deleting nodes from trie
3.
Algorithm for deleting nodes from trie
4.
Code in C++
5.
Complexity Analysis for deleting nodes from trie:
6.
Time Complexity 
7.
Space Complexity 
8.
Frequently Asked Questions
9.
Key Takeaways
Last Updated: Mar 27, 2024

Delete nodes from trie

Author Sneha Mallik
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction to tries
 

Trie is a tree data structure used for storing collections of words/trie nodes in the form of strings. If two strings have a common prefix, then they will have the same ancestor in the tree. We can use trie to store hundreds of thousands of strings, making it easy to search a string if it exists. 
 

For example - Dictionary is a trie data structure.

GIF Credits: giphy
 

Searching words is a laborious process but using tries makes it efficient and simpler.
 

Trie is an ideal data structure and is very much similar to the construction of trees. Tries are also used to do a prefix-based search, and we can sort the strings lexicographically in the trie. An alternative method is to use a hash table, but it has some drawbacks over trie since it cannot do a prefix-based search and a regular hash table takes more space than a trie. While deleting keys or words in a trie, we use recursion in a bottom-up manner.

Working of the Code for deleting nodes from trie

Let us consider an example. Suppose we have strings “ abc ”, “ abcf ” and “ kmn ” in our trie data structure, and we will delete the string “ abcf ”.

 

As we have to delete the string “ abcf ”, the first element to search in the trie data structure is the character ‘a’ in the root trie node.

 

Since ‘a’ is present in the root node, we will move the pointer to the next character in the string. We will then search for the next character in the trie data structure, i.e.,- character ‘b’.

 

Since ‘b’ exists in the node, we will move to the next pointer and search for the next character in the trie data structure, i.e.,- character ‘c’.

 

Notice that ‘c’ is also present in the next node, we will move the pointer to the next character in the string and search for the next character, ‘f’.

 

‘f’ is also present in the next node, we will move the pointer to the next node.

 

This trie node has no children because its data value is empty, so we can easily delete this node and move up to the higher level.
 

Since the end is false, we can easily delete this data value and the node and move to the next higher level.

 

Now here, we cannot delete this node as if we delete this node; then string “ abc ” will not be available when searching. Hence we stop here and we have deleted the string “ abcf ”.

Algorithm for deleting nodes from trie

 

When building a trie, the first element to be created or initialized is the root element before inserting any element. 

 

The root value will have a variable ‘wordEnd’ = 0; the wordEnd variable will indicate if the word has ended or not. If the word has finished, then we will increment the wordEnd variable by 1.

 

The root will create 26 pointers which will correspond to the child nodes.

struct Trienode{
    char data;
    int wordEnd; 

    /*
        A single node will be having 26 children as we have 26 
        alphabets
    */
    Trienode *child[26];
}

 

While performing the delete operation, we will be deleting the key using recursion in a bottom-up way.
 

The first case will be to check if the key exists or not in the trie data structure. We have to make sure that deleting nodes from trie should not modify the trie.
 

For example: 

WORDS: [“apple”, “ball”, “car”, “dog”, “dogecoin”, “carter”, “balling”]
 

We want to delete the string “best”.
 

We will search for the word “best” in the trie, but since it does not exist, hence no deletion will occur.
 

The second case is that the key should be unique, i.e., no part of the key should contain any other key, nor the key itself will have another key. Then we can delete all the nodes.
 

For example, we can delete “apple” as it is a unique key.

 

The third case is when the key itself is a prefix of another key in the trie data structure. (Prefix case)

 

For example, we want to delete “car” but “car” is also present in “carter”. Hence, we will update the leaf node boolean value “true” to ”false” for the string “car”. 
 

The fourth case is when the key we are deleting has another key as its prefix.
 

For example, we want to delete “balling”. So we can delete all the nodes from the bottom till we reach the leaf node for the word “ball”. Hence, we will delete 3 characters “g”, “n” and then “i”. 

 

The fifth case is when a node is later on shared with other words

 

For example, we want to delete the word “dogecoin” which is also a part of “dog”. We will check if any other children are there in “d”; there is one child; hence, we move on to “o”, we notice that it is common for “dog” too. Here we will delete the remaining nodes “e”, “c”, ”o”, ”i” and ”n”; hence, the word “dogecoin” is deleted.  

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Code in C++

// Program for deleting nodes from trie

#include <bits/stdc++.h>
using namespace std;

const int numChar = 26;

// Trie node structure
struct Trienode{
    struct Trienode *child[numChar];
    bool wordEnd;
};

/*
    Function to create the node which returns new trieNode initialized 
    to NULL
*/
struct Trienode *createNode(void){
    struct Trienode *newNodenew Trienode;
    newNode->wordEnd = false;
    
    for(int i = 0 ; i < numChar ; i++)
        newNode->child[i] = NULL;
        
    return newNode;
}

/*
    If a node is not present, it will insert a word to the trie; if the 
    word is a prefix of trie node, and it will just mark the leaf node
*/
void trieInsert(struct Trienode *root, string word){
    struct Trienode *temproot;

    for(int i = 0 ; i < word.length() ; i++){
        int index = word[i] - 'a';
        if(!temp->child[index]){
            
            // To create a new node
            temp->child[index] = createNode();
        }
        temp = temp->child[index];
    }

    // Indicates the last node as leaf
    temp->wordEnd = true;
}

// Function for searching word in the trie and return true if present
bool trieSearch(struct Trienode *root, string word){
    struct Trienode *temproot;

    for(int i = 0 ; i < word.length() ; i++){
        int index = word[i] - 'a';
        if(!temp->child[index]){
            return false;
        }
        temp = temp->child[index];
    }
    return (temp != NULL && temp->wordEnd);
}

// Function to check if the root has any children or not.
bool trieEmpty(Trienode *root){
    for(int i = 0 ; i < numChar ; i++){
        if(root->child[i]){
            return false;
        }
    }    
    return true;
}

// Function having a recursive call to delete a word from the Trie given
Trienode* trieDelete(Trienode *root, string word, int height = 0){
    
    // Condition if the tree is empty
    if(!root){
        return NULL;
    }

    // The final character of the word is being handled
    if(height == word.size()){

        /*
            After removal of the given word/key, the last node is 
            not the end of the word
        */
        if(root->wordEnd){
            root->wordEnd = false;
        }

        // In case if the given word isn't prefix of any other word
        if(trieEmpty(root)){
            delete (root);
            root = NULL;
        }
        return root;
    }

    /*
        In case it is not the last character, repeat for the child using 
        ASCII value
    */
    int index = word[height] - 'a';
    root->child[index] = trieDelete(root->child[index], word, height + 1);

    /*
        In case the root does not have any child(its only child gets 
        removed), then it is not the same for another word. The another 
        word does not end here.
    */
    if(trieEmpty(root) && root->wordEnd == false){
        // Node deleted
        delete(root); 
        root = NULL;
    }
    return root;
}

int main(){
    string word[] = {"coding""ninja""play""join""us""have"
    "fun"};
    int size = sizeof(word) / sizeof(word[0]);
    struct Trienode *rootcreateNode();

    // To construct the nodes in the trie
    for(int i = 0; i < size; i++){
        trieInsert(root, word[i]);
    }

    // To search for a word in the trie inputted
    trieSearch(root, "coding") ? cout << "Yes, it is present!\n"cout 
    << "No, it is not present!\n";
    
    trieSearch(root, "ninja") ? cout << "Yes, it is present!\n"cout 
    << "No, it is not present!\n";

    // To delete a word in the trie
    trieDelete(root, "play");
    
    // To search the word deleted
    trieSearch(root, "playground") ? cout << "Yes, it is present!\n"cout 
    << "No, it is not present!\n";
    return 0;
}

 

 

Output-

Yes, it is present!
Yes, it is present!
No, it is not present!

 

Complexity Analysis for deleting nodes from trie:

Time Complexity 

O(L) time complexity is used for insertion, searching and deletion in a trie data structure, where ‘L’ is the word length.

 

If the average length of a string/word is ‘L’ and there are ‘N’ number of words, then the time complexity will be O(L x N) for deleting a string in the trie data structure.

 

Space Complexity 

Each node can store up to 26 child pointers for 26 alphabets taking O(S) space complexity.

 

Each string can have a maximum length ‘M’ taking O(M) space complexity.
 

To store a string will take O(N) space complexity depending upon the number of strings.
 

Therefore, O(S) x O(M) x O(N) = O(S x M x N) space complexity.
 

O(S x M x N) space complexity is used in a trie data structure where ‘S’ is the size of the alphabet, ‘N’ is the total number of strings, and ‘M’ is the maximum length of the word.
 

Check out this problem - Longest Common Prefix 

Frequently Asked Questions

  1. What is a trie?

Trie is a tree-like data structure used to recover a word or key in a string dataset efficiently. It is also known as a prefix tree as its child nodes have a common prefix of the string associated with the node. The trie node’s position within the tree characterizes the key associated with it, and the key is only associated with the leaf nodes. It is also known as the ‘retrieval tree’.
 

2. What are the applications of tries?

Applications of trie are:

  • For auto completing words
  • Dictionary / Predictive text
  • For checking spellings
  • Longest prefix matching

 

3. What is a suffix tree in a trie data structure?

A suffix tree is a modified version of trie which is used in the case of matching patterns in a string which is a very efficient method as it is done in a linear time. We can use it to reduce the length of the long paths to search a string, reducing the size of the trie, hence improving the time complexity.
 

4. How is a trie different from a tree?

A trie is exceptionally distinctive from a tree as it stores sequences of values instead of single values. The trie does not hold its associated values/keys. Instead, the trie node position defines the value with which it is associated.

 

5. What is the difference between a trie and a set?

We can put the words either in a trie or a set. If we want to find words having the same first prefix, then we can use a trie. But if we want to know if a string exists or not, we can do it in a hash set as it optimizes space. 

Key Takeaways

In this blog, we learned about deleting nodes from trie, the working of trie with proper and clear diagrams, the code on deleting nodes from trie and its algorithm implementation.

 

Try problems on deleting nodes from trie, trie insertion and searching in trie problems here on Coding Ninjas Studio to understand the working algorithms of tries. To be more confident in data structures and algorithms, try out our DS and Algo Course.

Previous article
Substring Check Using Suffix Tree
Next article
Dictionaries using Tries
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass