Deletion in Trie Data Structure

This operation is used to delete strings from the Trie data structure. There are three cases when deleting a word from Trie.

The deleted word is a prefix of other words in Trie.
The deleted word shares a common prefix with other words in Trie.
The deleted word does not share any common prefix with other words in Trie.

3.1 The deleted word is a prefix of other words in Trie.

As shown in the following figure, the deleted word “an” share a complete prefix with another word “and” and “ant“.

Deletion of word which is a prefix of other words in Trie

An easy solution to perform a delete operation for this case is to just decrement the wordCount by 1 at the ending node of the word.

3.2 The deleted word shares a common prefix with other words in Trie.

As shown in the following figure, the deleted word “and” has some common prefixes with other words ‘ant’. They share the prefix ‘an’.

Deletion of word which shares a common prefix with other words in Trie

The solution for this case is to delete all the nodes starting from the end of the prefix to the last character of the given word.

3.3 The deleted word does not share any common prefix with other words in Trie.

As shown in the following figure, the word “geek” does not share any common prefix with any other words.

The solution for this case is just to delete all the nodes.

Below is the implementation that handles all the above cases:

C++

bool delete_key(TrieNode* root, string& word)
{
    TrieNode* currentNode = root;
    TrieNode* lastBranchNode = NULL;
    char lastBrachChar = 'a';

    for (auto c : word) {
        if (currentNode->childNode[c - 'a'] == NULL) {
            return false;
        }
        else {
            int count = 0;
            for (int i = 0; i < 26; i++) {
                if (currentNode->childNode[i] != NULL)
                    count++;
            }

            if (count > 1) {
                lastBranchNode = currentNode;
                lastBrachChar = c;
            }
            currentNode = currentNode->childNode[c - 'a'];
        }
    }

    int count = 0;
    for (int i = 0; i < 26; i++) {
        if (currentNode->childNode[i] != NULL)
            count++;
    }

    // Case 1: The deleted word is a prefix of other words
    // in Trie.
    if (count > 0) {
        currentNode->wordCount--;
        return true;
    }

    // Case 2: The deleted word shares a common prefix with
    // other words in Trie.
    if (lastBranchNode != NULL) {
        lastBranchNode->childNode[lastBrachChar] = NULL;
        return true;
    }
    // Case 3: The deleted word does not share any common
    // prefix with other words in Trie.
    else {
        root->childNode[word[0]] = NULL;
        return true;
    }
}

Java

public class TrieNode {
    TrieNode[] childNode;
    int wordCount;

    public TrieNode() {
        this.childNode = new TrieNode[26];
        this.wordCount = 0;
    }
}

public class Trie {
    TrieNode root;

    public Trie() {
        this.root = new TrieNode();
    }

    public boolean deleteKey(String word) {
        TrieNode currentNode = root;
        TrieNode lastBranchNode = null;
        char lastBranchChar = 'a';

        for (char c : word.toCharArray()) {
            if (currentNode.childNode[c - 'a'] == null) {
                // If the current node has no child, the word is not present
                return false;
            } else {
                int count = 0;
                // Count the number of non-null child nodes
                for (int i = 0; i < 26; i++) {
                    if (currentNode.childNode[i] != null)
                        count++;
                }

                if (count > 1) {
                    // If there are more than one child, store the last branch information
                    lastBranchNode = currentNode;
                    lastBranchChar = c;
                }
                currentNode = currentNode.childNode[c - 'a'];
            }
        }

        int count = 0;
        // Count the number of non-null child nodes at the last character
        for (int i = 0; i < 26; i++) {
            if (currentNode.childNode[i] != null)
                count++;
        }

        // Case 1: The deleted word is a prefix of other words in Trie.
        if (count > 0) {
            // Decrement the word count and indicate successful deletion
            currentNode.wordCount--;
            return true;
        }

        // Case 2: The deleted word shares a common prefix with other words in Trie.
        if (lastBranchNode != null) {
            // Remove the link to the deleted word
            lastBranchNode.childNode[lastBranchChar - 'a'] = null;
            return true;
        }
        // Case 3: The deleted word does not share any common prefix with other words in Trie.
        else {
            // Remove the link to the deleted word from the root
            root.childNode[word.charAt(0) - 'a'] = null;
            return true;
        }
    }
}

Python3

def delete_key(root, word):
    current_node = root
    last_branch_node = None
    last_branch_char = 'a'

    # loop through each character in the word
    for c in word:
        # if the current node doesn't have a child with the current character,
        # return False as the word is not present in Trie
        if current_node.childNode[ord(c) - ord('a')] is None:
            return False
        else:
            count = 0
            # count the number of children nodes of the current node
            for i in range(26):
                if current_node.childNode[i] is not None:
                    count += 1

            # if the count of children is more than 1,
            # store the node and the current character
            if count > 1:
                last_branch_node = current_node
                last_branch_char = c

            current_node = current_node.childNode[ord(c) - ord('a')]

    count = 0
    # count the number of children nodes of the current node
    for i in range(26):
        if current_node.childNode[i] is not None:
            count += 1

    # Case 1: The deleted word is a prefix of other words in Trie
    if count > 0:
        current_node.wordCount -= 1
        return True

    # Case 2: The deleted word shares a common prefix with other words in Trie
    if last_branch_node is not None:
        last_branch_node.childNode[ord(last_branch_char) - ord('a')] = None
        return True

    # Case 3: The deleted word does not share any common prefix with other words in Trie
    else:
        root.childNode[ord(word[0]) - ord('a')] = None
        return True

public bool delete_key(TrieNode root, string word)
{
    TrieNode current_node = root;
    TrieNode last_branch_node = null;
    char last_branch_char = 'a';

    // loop through each character in the word
    foreach (char c in word)
    {
        // if the current node doesn't have a child with the current character,
        // return False as the word is not present in Trie
        if (current_node.childNode[c - 'a'] == null)
        {
            return false;
        }
        else
        {
            int count = 0;
            // count the number of children nodes of the current node
            for (int i = 0; i < 26; i++)
            {
                if (current_node.childNode[i] != null)
                {
                    count++;
                }
            }

            // if the count of children is more than 1,
            // store the node and the current character
            if (count > 1)
            {
                last_branch_node = current_node;
                last_branch_char = c;
            }

            current_node = current_node.childNode[c - 'a'];
        }
    }

    int wordCount = 0;
    // count the number of children nodes of the current node
    for (int i = 0; i < 26; i++)
    {
        if (current_node.childNode[i] != null)
        {
            wordCount++;
        }
    }

    // Case 1: The deleted word is a prefix of other words in Trie
    if (wordCount > 0)
    {
        current_node.wordCount--;
        return true;
    }

    // Case 2: The deleted word shares a common prefix with other words in Trie
    if (last_branch_node != null)
    {
        last_branch_node.childNode[last_branch_char - 'a'] = null;
        return true;
    }

    // Case 3: The deleted word does not share any common prefix with other words in Trie
    else
    {
        root.childNode[word[0] - 'a'] = null;
        return true;
    }
}

//This code is contributed by shivamsharma215

Javascript

function delete_key(root, word) {
    let currentNode = root;
    let lastBranchNode = null;
    let lastBrachChar = 'a';

    for (let c of word) {
        if (currentNode.childNode[c.charCodeAt(0) - 'a'.charCodeAt(0)] === null) {
            return false;
        } else {
            let count = 0;
            for (let i = 0; i < 26; i++) {
                if (currentNode.childNode[i] !== null) {
                    count++;
                }
            }

            if (count > 1) {
                lastBranchNode = currentNode;
                lastBrachChar = c;
            }
            currentNode = currentNode.childNode[c.charCodeAt(0) - 'a'.charCodeAt(0)];
        }
    }

    let count = 0;
    for (let i = 0; i < 26; i++) {
        if (currentNode.childNode[i] !== null) {
            count++;
        }
    }

    // Case 1: The deleted word is a prefix of other words
    // in Trie.
    if (count > 0) {
        currentNode.wordCount--;
        return true;
    }

    // Case 2: The deleted word shares a common prefix with
    // other words in Trie.
    if (lastBranchNode !== null) {
        lastBranchNode.childNode[lastBrachChar] = null;
        return true;
    }
    // Case 3: The deleted word does not share any common
    // prefix with other words in Trie.
    else {
        root.childNode[word[0].charCodeAt(0) - 'a'.charCodeAt(0)] = null;
        return true;
    }
}

//This code is contributed by shivamsharma215

Trie Data Structure Tutorial

The trie data structure, also known as a prefix tree, is a tree-like data structure used for efficient retrieval of key-value pairs. It is commonly used for implementing dictionaries and autocomplete features, making it a fundamental component in many search algorithms. In this article, we will explore all about Trie data structures in detail.

Trie Data Structure

Table of Content

What is Trie Data Structure?
What is need of Trie Data Structure?
Advantages of Trie Data Structure over a Hash Table
Properties of a Trie Data Structure
How does Trie Data Structure work?
Representation of Trie Node
Basic Operations on Trie Data Structure
Insertion in Trie Data Structure
Searching in Trie Data Structure
Deletion in Trie Data Structure
Implement Trie Data Structure?
Complexity Analysis of Trie Data Structure
Applications of Trie data structure
Advantages of Trie data structure
Disadvantages of Trie data structure
Top Interview problems on Trie data structure

Deletion in Trie Data Structure

3.1 The deleted word is a prefix of other words in Trie.

3.2 The deleted word shares a common prefix with other words in Trie.

3.3 The deleted word does not share any common prefix with other words in Trie.

Trie Data Structure Tutorial

Categories

Contact US

Deletion in Trie Data Structure

3.1 The deleted word is a prefix of other words in Trie.

3.2 The deleted word shares a common prefix with other words in Trie.

3.3 The deleted word does not share any common prefix with other words in Trie.

Trie Data Structure Tutorial

Similar Reads

Categories

Contact US