Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
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.
9.
Key Takeaways
Last Updated: Mar 27, 2024

# Delete nodes from trie

Sneha Mallik
0 upvote
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
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.

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

Output-

## 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.

Guided path
Free
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
Earn badges and level up
Live masterclass