Trie | (Delete)

Last Updated : 21 Feb, 2023

In the previous post on trie we have described how to insert and search a node in trie. Here is an algorithm how to delete a node from trie.
During delete operation we delete the key in bottom up manner using recursion. The following are possible conditions when deleting key from trie,

Key may not be there in trie. Delete operation should not modify trie.
Key present as unique key (no part of key contains another key (prefix), nor the key itself is prefix of another key in trie). Delete all the nodes.
Key is prefix key of another long key in trie. Unmark the leaf node.
Key present in trie, having atleast one other key as prefix key. Delete nodes from end of key until first leaf node of longest prefix key.

The below code presents algorithm to implement above conditions.

C++

// C++ implementation of delete
// operations on Trie
#include <bits/stdc++.h>
using namespace std;
 
const int ALPHABET_SIZE = 26;
 
// trie node
struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
 
    // isEndOfWord is true if the node represents
    // end of a word
    bool isEndOfWord;
};
 
// Returns new trie node (initialized to NULLs)
struct TrieNode* getNode(void)
{
    struct TrieNode* pNode = new TrieNode;
 
    pNode->isEndOfWord = false;
 
    for (int i = 0; i < ALPHABET_SIZE; i++)
        pNode->children[i] = NULL;
 
    return pNode;
}
 
// If not present, inserts key into trie
// If the key is prefix of trie node, just
// marks leaf node
void insert(struct TrieNode* root, string key)
{
    struct TrieNode* pCrawl = root;
 
    for (int i = 0; i < key.length(); i++) {
        int index = key[i] - 'a';
        if (!pCrawl->children[index])
            pCrawl->children[index] = getNode();
 
        pCrawl = pCrawl->children[index];
    }
 
    // mark last node as leaf
    pCrawl->isEndOfWord = true;
}
 
// Returns true if key presents in trie, else
// false
bool search(struct TrieNode* root, string key)
{
    struct TrieNode* pCrawl = root;
 
    for (int i = 0; i < key.length(); i++) {
        int index = key[i] - 'a';
        if (!pCrawl->children[index])
            return false;
 
        pCrawl = pCrawl->children[index];
    }
 
    return (pCrawl != NULL && pCrawl->isEndOfWord);
}
 
// Returns true if root has no children, else false
bool isEmpty(TrieNode* root)
{
    for (int i = 0; i < ALPHABET_SIZE; i++)
        if (root->children[i])
            return false;
    return true;
}
 
// Recursive function to delete a key from given Trie
TrieNode* remove(TrieNode* root, string key, int depth = 0)
{
    // If tree is empty
    if (!root)
        return NULL;
 
    // If last character of key is being processed
    if (depth == key.size()) {
 
        // This node is no more end of word after
        // removal of given key
        if (root->isEndOfWord)
            root->isEndOfWord = false;
 
        // If given is not prefix of any other word
        if (isEmpty(root)) {
            delete (root);
            root = NULL;
        }
 
        return root;
    }
 
    // If not last character, recur for the child
    // obtained using ASCII value
    int index = key[depth] - 'a';
    root->children[index] = 
          remove(root->children[index], key, depth + 1);
 
    // If root does not have any child (its only child got 
    // deleted), and it is not end of another word.
    if (isEmpty(root) && root->isEndOfWord == false) {
        delete (root);
        root = NULL;
    }
 
    return root;
}
 
// Driver
int main()
{
    // Input keys (use only 'a' through 'z'
    // and lower case)
    string keys[] = { "the", "a", "there",
                      "answer", "any", "by",
                      "bye", "their", "hero", "heroplane" };
    int n = sizeof(keys) / sizeof(keys[0]);
 
    struct TrieNode* root = getNode();
 
    // Construct trie
    for (int i = 0; i < n; i++)
        insert(root, keys[i]);
 
    // Search for different keys
    search(root, "the") ? cout << "Yes\n" : cout << "No\n";
    search(root, "these") ? cout << "Yes\n" : cout << "No\n";
 
    remove(root, "heroplane");
    search(root, "hero") ? cout << "Yes\n" : cout << "No\n";
    return 0;
}

Java

// Java implementation of delete
// operations on Trie
import java.util.*;
 
public class GFG{
     
    static int ALPHABET_SIZE = 26;
 
    // trie node
    static class TrieNode {
        TrieNode children[] = new TrieNode[ALPHABET_SIZE];
 
        // isEndOfWord is true if the node represents
        // end of a word
        boolean isEndOfWord;
    }
 
 
    // If not present, inserts key into trie
    // If the key is prefix of trie node, just
    // marks leaf node
    static void insert(TrieNode root, String key)
    {
        TrieNode pCrawl = root;
 
        for (int i = 0; i < key.length(); i++) {
            int index = key.charAt(i) - 'a';
            if (pCrawl.children[index] == null)
                pCrawl.children[index] = new TrieNode();
 
            pCrawl = pCrawl.children[index];
        }
 
        // mark last node as leaf
        pCrawl.isEndOfWord = true;
    }
 
    // Returns true if key presents in trie, else
    // false
    static boolean search(TrieNode root, String key)
    {
        TrieNode pCrawl = root;
 
        for (int i = 0; i < key.length(); i++) {
            int index = key.charAt(i) - 'a';
            if (pCrawl.children[index] == null)
                return false;
 
            pCrawl = pCrawl.children[index];
        }
 
        return (pCrawl != null && pCrawl.isEndOfWord);
    }
 
    // Returns true if root has no children, else false
    static boolean isEmpty(TrieNode root)
    {
        for (int i = 0; i < ALPHABET_SIZE; i++)
            if (root.children[i] != null)
                return false;
        return true;
    }
 
    // Recursive function to delete a key from given Trie
    static TrieNode remove(TrieNode root, String key, int depth)
    {
        // If tree is empty
        if (root == null)
            return null;
 
        // If last character of key is being processed
        if (depth == key.length()) {
 
            // This node is no more end of word after
            // removal of given key
            if (root.isEndOfWord)
                root.isEndOfWord = false;
 
            // If given is not prefix of any other word
            if (isEmpty(root)) {
                root = null;
            }
 
            return root;
        }
 
        // If not last character, recur for the child
        // obtained using ASCII value
        int index = key.charAt(depth) - 'a';
        root.children[index] =
            remove(root.children[index], key, depth + 1);
 
        // If root does not have any child (its only child got
        // deleted), and it is not end of another word.
        if (isEmpty(root) && root.isEndOfWord == false){ 
            root = null;
        }
 
        return root;
    }
 
    // Driver
    public static void main(String args[])
    {
        // Input keys (use only 'a' through 'z'
        // and lower case)
        String keys[] = { "the", "a", "there",
                        "answer", "any", "by",
                        "bye", "their", "hero", "heroplane" };
        int n = keys.length;
 
        TrieNode root = new TrieNode();
 
        // Construct trie
        for (int i = 0; i < n; i++)
            insert(root, keys[i]);
 
        // Search for different keys
        if(search(root, "the"))
            System.out.println("Yes");
        else
            System.out.println("No");
 
        if(search(root, "these"))
            System.out.println("Yes");
        else
            System.out.println("No");
 
        remove(root, "heroplane", 0);
         
        if(search(root, "hero"))
            System.out.println("Yes");
        else
            System.out.println("No");
 
    }
}
 
// This code is contributed by aditypande88.

Python3

class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.isEndOfWord = False
 
def getNode():
    pNode = TrieNode()
    pNode.isEndOfWord = False
    return pNode
 
def insert(root, key):
    pCrawl = root
    for i in range(len(key)):
        index = ord(key[i]) - ord('a')
        if not pCrawl.children[index]:
            pCrawl.children[index] = getNode()
        pCrawl = pCrawl.children[index]
    pCrawl.isEndOfWord = True
 
def search(root, key):
    pCrawl = root
    for i in range(len(key)):
        index = ord(key[i]) - ord('a')
        if not pCrawl.children[index]:
            return False
        pCrawl = pCrawl.children[index]
    return pCrawl and pCrawl.isEndOfWord
 
def isEmpty(root):
    for i in range(26):
        if root.children[i]:
            return False
    return True
 
def remove(root, key, depth = 0):
    if not root:
        return None
 
    if depth == len(key):
        if root.isEndOfWord:
            root.isEndOfWord = False
        if isEmpty(root):
            del root
            root = None
        return root
 
    index = ord(key[depth]) - ord('a')
    root.children[index] = remove(root.children[index], key, depth + 1)
 
    if isEmpty(root) and not root.isEndOfWord:
        del root
        root = None
    return root
 
if __name__ == '__main__':
    keys = ["the", "a", "there", "answer", "any", "by", "bye", "their", "hero", "heroplane"]
    root = getNode()
    for i in range(len(keys)):
        insert(root, keys[i])
    if search(root, "the"):
        print("Yes")
    else:
        print("No")
    if search(root, "these"):
        print("Yes")
    else:
        print("No")
    root = remove(root, "heroplane")
    if search(root, "hero"):
        print("Yes")
    else:
        print("No")

C#

// C# implementation of delete
// operations on Trie
using System;
 
namespace GFG
{
    class TrieNode
    {
        // An array of children nodes.
        public TrieNode[] children = new TrieNode[26];
 
        // A flag to represent end of a word.
        public bool isEndOfWord;
    }
 
    class Program
    {
        static int ALPHABET_SIZE = 26;
 
        static void Insert(TrieNode root, string key)
        {
            // Start from root node.
            TrieNode pCrawl = root;
 
            for (int i = 0; i < key.Length; i++)
            {
                int index = key[i] - 'a';
 
                // Create a new node if the path doesn't exist.
                if (pCrawl.children[index] == null)
                    pCrawl.children[index] = new TrieNode();
 
                // Move to the next node.
                pCrawl = pCrawl.children[index];
            }
 
            // Mark the last node as the end of a word.
            pCrawl.isEndOfWord = true;
        }
 
        static bool Search(TrieNode root, string key)
        {
            // Start from the root node.
            TrieNode pCrawl = root;
 
            for (int i = 0; i < key.Length; i++)
            {
                int index = key[i] - 'a';
 
                // If the path doesn't exist, return false.
                if (pCrawl.children[index] == null)
                    return false;
 
                // Move to the next node.
                pCrawl = pCrawl.children[index];
            }
 
            // Return true if the last node represents the end of a word.
            return (pCrawl != null && pCrawl.isEndOfWord);
        }
 
        static bool IsEmpty(TrieNode root)
        {
            for (int i = 0; i < ALPHABET_SIZE; i++)
                if (root.children[i] != null)
                    return false;
 
            return true;
        }
 
        static TrieNode Remove(TrieNode root, string key, int depth)
        {
            // If tree is empty.
            if (root == null)
                return null;
 
            // If last character of key is being processed.
            if (depth == key.Length)
            {
                // This node is no more end of word after
                // removal of given key.
                if (root.isEndOfWord)
                    root.isEndOfWord = false;
 
                // If given key is not a prefix of any other word.
                if (IsEmpty(root))
                    root = null;
 
                return root;
            }
 
            // If not last character, recur for the child obtained by
            // indexing into the children array using the current character.
            int index = key[depth] - 'a';
            root.children[index] = Remove(root.children[index], key, depth + 1);
 
            // If root does not have any children (its only child got
            // deleted), and it is not the end of a word.
            if (IsEmpty(root) && !root.isEndOfWord)
                root = null;
 
            return root;
        }
 
        static void Main(string[] args)
        {
            // Test cases.
            string[] keys = { "the", "a", "there", "answer", "any", 
                               "by", "bye", "their", "hero", "heroplane" };
            int n = keys.Length;
 
            // Construct the Trie.
            TrieNode root = new TrieNode();
            for (int i = 0; i < n; i++)
                Insert(root, keys[i]);
 
            // Test search function.
 
            if (Search(root, "the"))
                Console.WriteLine("Yes");
            else
                Console.WriteLine("No");
 
            if (Search(root, "these"))
                Console.WriteLine("Yes");
            else
                Console.WriteLine("No");
 
            Remove(root, "heroplane", 0);
 
            if (Search(root, "hero"))
                Console.WriteLine("Yes");
            else
                Console.WriteLine("No");
 
            Console.ReadLine();
        }
    }
}

Javascript

<script>
// Javascript implementation of delete
// operations on Trie
 
let ALPHABET_SIZE = 26;
 
// trie node
class TrieNode
{
    constructor()
    {
        this.children=new Array(ALPHABET_SIZE);
        this.isEndOfWord=false;
    }
}
 
// If not present, inserts key into trie
    // If the key is prefix of trie node, just
    // marks leaf node
function insert(root,key)
{
    let pCrawl = root;
  
        for (let i = 0; i < key.length; i++) {
            let index = key[i].charCodeAt(0) - 'a'.charCodeAt(0);
            if (pCrawl.children[index] == null)
                pCrawl.children[index] = new TrieNode();
  
            pCrawl = pCrawl.children[index];
        }
  
        // mark last node as leaf
        pCrawl.isEndOfWord = true;
}
 
// Returns true if key presents in trie, else
    // false
function search(root,key)
{
    let pCrawl = root;
  
        for (let i = 0; i < key.length; i++) {
            let index = key[i].charCodeAt(0) - 'a'.charCodeAt(0);
            if (pCrawl.children[index] == null)
                return false;
  
            pCrawl = pCrawl.children[index];
        }
  
        return (pCrawl != null && pCrawl.isEndOfWord);
}
 
// Returns true if root has no children, else false
function isEmpty(root)
{
    for (let i = 0; i < ALPHABET_SIZE; i++)
            if (root.children[i] != null)
                return false;
        return true;
}
 
// Recursive function to delete a key from given Trie
function remove(root,key,depth)
{
    // If tree is empty
        if (root == null)
            return null;
  
        // If last character of key is being processed
        if (depth == key.length) {
  
            // This node is no more end of word after
            // removal of given key
            if (root.isEndOfWord)
                root.isEndOfWord = false;
  
            // If given is not prefix of any other word
            if (isEmpty(root)) {
                root = null;
            }
  
            return root;
        }
  
        // If not last character, recur for the child
        // obtained using ASCII value
        let index = key[depth].charCodeAt(0) - 'a'.charCodeAt(0);
        root.children[index] =
            remove(root.children[index], key, depth + 1);
  
        // If root does not have any child (its only child got
        // deleted), and it is not end of another word.
        if (isEmpty(root) && root.isEndOfWord == false){
            root = null;
        }
  
        return root;
}
 
// Driver
// Input keys (use only 'a' through 'z'
// and lower case)
let keys = [ "the", "a", "there",
                 "answer", "any", "by",
                 "bye", "their", "hero", "heroplane" ];
let n = keys.length;
 
let root = new TrieNode();
 
// Construct trie
for (let i = 0; i < n; i++)
    insert(root, keys[i]);
 
// Search for different keys
if(search(root, "the"))
    document.write("Yes<br>");
else
    document.write("No<br>");
 
if(search(root, "these"))
    document.write("Yes<br>");
else
    document.write("No<br>");
 
remove(root, "heroplane", 0);
 
if(search(root, "hero"))
    document.write("Yes<br>");
else
    document.write("No<br>");
 
 
// This code is contributed by patel2127
</script>

Output:

Yes
No
Yes

Time Complexity: The time complexity of the deletion operation is O(n) where n is the key length.

Auxiliary Space: O(n*m), where n is the key length of the longest word and m is the total no of words.

https://youtu.be/XK8MD9N9WUA
— Venki.

GeeksforGeeks

Improve

Compressed Tries

Similar Reads

Sorting array of strings (or words) using Trie | Set-2 (Handling Duplicates)

Given an array of strings, print them in alphabetical (dictionary) order. If there are duplicates in input array, we need to print all the occurrences.Examples: Input : arr[] = { "abc", "xyz", "abcd", "bcd", "abc" } Output : abc abc abcd bcd xyz Input : arr[] = { "geeks", "for", "geeks", "a", "portal", "to", "learn" } Output : a for geeks geeks lea

Persistent Trie | Set 1 (Introduction)

Prerequisite: TriePersistency in Data Structure Trie is one handy data structure that often comes into play when performing multiple string lookups. In this post, we will introduce the concept of Persistency in this data structure. Persistency simply means to retain the changes. But obviously, retaining the changes cause extra memory consumption an

Bottom-up traversal of a Trie

Trie is an efficient information retrieval data structure. Using Trie, search complexities can be brought to an optimal limit (key length). Given a trie. The task is to print the characters in a bottom-up manner Bottom-up traversal: First print string of left most subtree(from bottom to top) then print string of second left subtree(from bottom to t

Check if the given Trie contains words starting from every alphabet

Given a Trie, the task is to check if it contains words starting from every alphabet from [a - z]. Examples: Input: keys[] = {"element", "fog", "great", "hi", "ok", "ios", "parrot", "quiz", "kim", "mango", "nature", "apple", "ball", "cat", "dog", "lime", "ruby", "shine", "tinkter", "ultra", "volly", "wow", "xerox", "yak", "zenon", "joke"} Output: Y

Implement a Dictionary using Trie

Implement a dictionary using Trie such that if the input is a string representing a word, the program prints its meaning from the prebuilt dictionary. Examples: Input: str = "map" Output: a diagrammatic representation of an area Input: str = "language" Output: the method of human communication Approach: We can use a Trie to efficiently store string

Insertion in a Trie recursively

Trie is an efficient information retrieval data structure. Using Trie, search complexities can be brought to an optimal limit (key length). Given multiple strings. The task is to insert the string in a Trie using recursion.Examples: Input : str = {"cat", "there", "caller", "their", "calling"} Output : caller calling cat there their root / \ c t | |

Search in a trie Recursively

Trie is an efficient information retrieval data structure. Using Trie, search complexities can be brought to an optimal limit (key length).The task is to search a string in a Trie using recursion.Examples : root / \ t a | | h n | | \ e s y / | | i r w | | | r e e | r Input : str = "anywhere" Output : not found Input : str = "answer" Output : found

Trie Data Structure using smart pointer and OOP in C++

We will implement trie using smart pointers in C++ and OOP. Here, We have already discussed the implementation of trie data using recursionIn our implementation node of a trie look like : C/C++ Code class TrieNode{ public: // Use of shared_ptr for storing Children // Pointers of TrieNode shared_ptr children[ALPHABET_SIZE]; // Tracks whether If this

Count inversions in an array | Set 4 ( Using Trie )

Inversion Count for an array indicates – how far (or close) the array is from being sorted. If the array is already sorted then inversion count is 0. If the array is sorted in reverse order that inversion count is the maximum. Two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j. For simplicity, we may assume that all element

Print all possible combinations of words from Dictionary using Trie

Given an array of strings arr[], for every string in the array, print all possible combinations of strings that can be concatenated to make that word. Examples: Input: arr[] = ["sam", "sung", "samsung"] Output: sam: sam sung: sung samsung: sam sung samsung String 'samsung' can be formed using two different strings from the array i.e. 'sam' and 'sun

Article Tags :

Practice Tags :