Trie Deletion and Applications

Deletion in a Trie is a recursive process. Since nodes in a Trie can be shared among different keys, we must be careful not to delete nodes that are part of other active words.

Deletion Cases

When deleting a key K from a Trie:

Case 1: The key is a prefix of another word

• Example: Delete "the" when "them" is also in the Trie.
• Action: Simply change the isEndOfWord flag of the last character of "the" to false. We do not delete any nodes.

Case 2: The key has a unique path but shares a prefix

• Example: Delete "geek" when "geeks" is in the Trie.
• Action: Delete nodes starting from the end of the word until we reach a node that is marked as isEndOfWord or has other children.

Case 3: The key has no prefix/suffix overlap

• Example: Delete "hero" when no other words starting with h exist.
• Action: Delete all nodes of "hero" from the root downward.

Deletion Implementation

We can write a recursive helper function remove that returns true if a node's child should be deleted (i.e. it has no other children and is not the end of another word).

class TrieNode {
    constructor() {
        this.children = new Array(26).fill(null);
        this.isEndOfWord = false;
    }
}
 
// Returns true if node has no children
function isEmpty(node) {
    for (let i = 0; i < 26; i++) {
        if (node.children[i] !== null) {
            return false;
        }
    }
    return true;
}
 
// Recursive function to delete a key from given Trie
function remove(root, key, depth = 0) {
    // 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 longer end of word after removal
        if (root.isEndOfWord) {
            root.isEndOfWord = false;
        }
 
        // If root does not have any other child, it can be deleted
        if (isEmpty(root)) {
            root = null;
        }
 
        return root;
    }
 
    // If not last character, recur for the child
    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, delete it
    if (isEmpty(root) && root.isEndOfWord === false) {
        root = null;
    }
 
    return root;
}

Applications of Trie

1. Auto-Complete / Search Suggestions: Used by browsers and search engines to show instant search predictions.
2. Spelling Checkers: Storing a vocabulary inside a Trie allows fast spell checking and prefix verification.
3. Longest Prefix Matching: Used in IP routing packets in routers to find the longest matching subnet mask.
4. Browser History/URL autocomplete: Swiftly searches previously visited website URLs.

Advantages and Disadvantages of Trie

Advantages:

• Fast Lookups: O(M) time complexity, completely independent of the number of keys N in the structure.
• Ordered Iteration: Easy traversal of keys in alphabetical order.
• Space efficiency for common prefixes: Shared prefixes save memory compared to storing complete duplicate strings.

Disadvantages:

• High Memory Overhead: Each node contains an array of 26 pointers (or more if uppercase/special characters are supported). Many of these pointers are null, causing sparse memory usage.
• Cache Misses: Trie nodes are allocated dynamically in memory, leading to poor cache locality compared to continuous array-based search structures.