L2. Implement Trie-2 | INSERT | countWordsEqualTo() | countWordsStartingWith() | C++ | Java

An advanced evolution of the standard Trie data structure that extends traditional insert and search capabilities to support multi-instance frequency tracking (countWordsEqualTo), prefix matching frequencies (countWordsStartingWith), and safe node de-allocation via erasure (erase).

1. Why Do We Need This? (Problem Statement & Limitations of Trie-1)

In the standard Trie (Trie-1), each node maintains a boolean flag (isEnd) indicating whether a valid word terminates at that exact character. While efficient for binary existence checks (i.e., Does this exact word exist? or Does any word start with this prefix?), Trie-1 breaks down completely when dealing with frequency and multiplicity requirements:

• Duplicate Words: If a word like "samsung" is inserted twice, a boolean flag cannot distinguish between 1 occurrence and 50 occurrences.
• Quantifying Prefixes: A boolean cannot tell us how many words share a specific prefix (e.g., how many words start with "app").
• Deletion Handling: Simply flipping a boolean flag to false during deletion risks breaking shared prefixes of other active words.

The Four Core Functionalities

1. insert(word): Adds a word into the Trie while incrementing structural frequency counters.
2. countWordsEqualTo(word): Returns the exact number of times a specific word has been inserted.
3. countWordsStartingWith(prefix): Returns the total count of stored words that share the given prefix.
4. erase(word): Decrements frequency counters along the path of the word without destroying shared structural branches.

2. Core Mental Model & Frequency Tracking Variables

Instead of relying solely on a boolean flag (endWith = true/false), the enhanced Trie node replaces it with two integer counters:

• endWith: Counts how many exact words terminate at this specific node.
• countPrefix: Counts how many inserted words pass through or terminate at this node (acting as a traffic counter for prefixes).

Real-Life Analogy: The City Postal Sorting Office

Imagine a central postal sorting facility (root) routing mail through 26 different outgoing conveyor belts (representing English alphabet letters a through z).

• Every time a letter passes through a sorting bin, the workers increment a footfall counter (countPrefix) attached to that bin.
• When a letter completes an address and drops into a final delivery box, workers increment a completion counter (endWith) on that box.
• If a package is recalled (erase), workers walk backward along the exact route, decrementing the footfall and completion counters without dismantling the physical sorting bins themselves.

3. Structural Evolution: Trie Node Architecture

Let's look at how the data structure transitions from a basic boolean flag model to our frequency-tracking integer model.

Naive / Standard Trie-1 Node

class Node {
    Node[] links = new Node[26];
    boolean flag = false; // Only tells if a word ends here
}

Enhanced Trie-2 Node (Production Ready)

class Node {
    Node[] links = new Node[26];
    int countEndWith = 0;   // Tracks exact word completions
    int countPrefix = 0;    // Tracks prefix traversal frequency

    boolean containsKey(char ch) {
        return links[ch - 'a'] != null;
    }

    Node get(char ch) {
        return links[ch - 'a'];
    }

    void put(char ch, Node node) {
        links[ch - 'a'] = node;
    }

    void increaseEnd() {
        countEndWith++;
    }

    void increasePrefix() {
        countPrefix++;
    }

    void deleteEnd() {
        countEndWith--;
    }

    void reducePrefix() {
        countPrefix--;
    }
}

4. Step-by-Step Flow Walkthrough: The Insertion Workflow

When inserting words into Trie-2, we traverse character by character from the root. If a character link does not exist, we instantiate a new Node. At every single step of the traversal, we increment countPrefix, and upon reaching the final character, we increment countEndWith.

Insertion Trace Example

Let's trace inserting the sequence: apple, apple, apps, appss.

5. Complete Code Implementation (Java & C++)

Below are the robust, production-grade implementations for both Java and C++.

Java Implementation

class Node {
    Node[] links = new Node[26];
    int countEndWith = 0;
    int countPrefix = 0;

    boolean containsKey(char ch) {
        return links[ch - 'a'] != null;
    }

    Node get(char ch) {
        return links[ch - 'a'];
    }

    void put(char ch, Node node) {
        links[ch - 'a'] = node;
    }

    void increaseEnd() {
        countEndWith++;
    }

    void increasePrefix() {
        countPrefix++;
    }

    void deleteEnd() {
        countEndWith--;
    }

    void reducePrefix() {
        countPrefix--;
    }

    int getEnd() {
        return countEndWith;
    }

    int getPrefix() {
        return countPrefix;
    }
}

public class Trie {
    private static Node root;

    public Trie() {
        root = new Node();
    }

    public void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (!node.containsKey(ch)) {
                node.put(ch, new Node());
            }
            node = node.get(ch);
            node.increasePrefix();
        }
        node.increaseEnd();
    }

    public int countWordsEqualTo(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (node.containsKey(ch)) {
                node = node.get(ch);
            } else {
                return 0;
            }
        }
        return node.getEnd();
    }

    public int countWordsStartingWith(String prefix) {
        Node node = root;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            if (node.containsKey(ch)) {
                node = node.get(ch);
            } else {
                return 0;
            }
        }
        return node.getPrefix();
    }

    public void erase(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (node.containsKey(ch)) {
                node = node.get(ch);
                node.reducePrefix();
            } else {
                return;
            }
        }
        node.deleteEnd();
    }
}

C++ Implementation

#include <iostream>
#include <string>
using namespace std;

struct Node {
    Node* links[26];
    int countEndWith = 0;
    int countPrefix = 0;

    bool containsKey(char ch) {
        return (links[ch - 'a'] != NULL);
    }

    void put(char ch, Node* node) {
        links[ch - 'a'] = node;
    }

    Node* get(char ch) {
        return links[ch - 'a'];
    }

    void increaseEnd() {
        countEndWith++;
    }

    void increasePrefix() {
        countPrefix++;
    }

    void deleteEnd() {
        countEndWith--;
    }

    void reducePrefix() {
        countPrefix--;
    }

    int getEnd() {
        return countEndWith;
    }

    int getPrefix() {
        return countPrefix;
    }
};

class Trie {
private:
    Node* root;

public:
    Trie() {
        root = new Node();
    }

    void insert(string word) {
        Node* node = root;
        for (int i = 0; i < word.length(); i++) {
            if (!node->containsKey(word[i])) {
                node->put(word[i], new Node());
            }
            node = node->get(word[i]);
            node->increasePrefix();
        }
        node->increaseEnd();
    }

    int countWordsEqualTo(string word) {
        Node* node = root;
        for (int i = 0; i < word.length(); i++) {
            if (node->containsKey(word[i])) {
                node = node->get(word[i]);
            } else {
                return 0;
            }
        }
        return node->getEnd();
    }

    int countWordsStartingWith(string prefix) {
        Node* node = root;
        for (int i = 0; i < prefix.length(); i++) {
            if (node->containsKey(prefix[i])) {
                node = node->get(prefix[i]);
            } else {
                return 0;
            }
        }
        return node->getPrefix();
    }

    void erase(string word) {
        Node* node = root;
        for (int i = 0; i < word.length(); i++) {
            if (node->containsKey(word[i])) {
                node = node->get(word[i]);
                node->reducePrefix();
            } else {
                return;
            }
        }
        node->deleteEnd();
    }
};

6. Comparison: Trie vs. Hash Maps for Substring/Prefix Queries

7. Industry Reality & Debugging Edge Cases

When deploying Tries in high-performance production environments, engineers must account for several common pitfalls:

• Null Pointer Exceptions (NPE): Attempting to query or erase a word whose prefix does not exist in the Trie will crash the program if boundary checks (containsKey) are omitted. Always verify branch existence before calling .get().
• Memory Leaks in C++: In languages like C++, nodes allocated dynamically via new Node() during insertion should ideally be freed recursively in a destructor during teardown. However, in competitive programming and interview settings, memory recycling via garbage collection or persistent root allocation is standard.
• Underflow on Erasure: Calling erase() on a word that was never inserted can cause negative counter values (countPrefix < 0 or countEndWith < 0). Ensure validation logic guarantees the word exists prior to deletion.

Summary and Key Takeaways

• - Extension of Trie-1: Trie-2 upgrades standard boolean existence flags into integer frequency trackers (countEndWith and countPrefix).
• **- Exact Word Counting (countWordsEqualTo): Returns the exact multiplicity of an inserted word in $O(L)$ time complexity.
• **- Prefix Frequency Counting (countWordsStartingWith): Instantly calculates how many active words pass through a particular prefix node.
• **- Safe Erasure (erase): Decrements prefix and termination counters along the path without breaking shared character branches for other words.
• **- Memory Optimization: Tries outperform Hash Maps for prefix-heavy operations by sharing common character nodes.
• **- Time Complexity: All primary operations (insert, search, count, erase) execute in **$O(L)** time, where$L$ is the length of the word/prefix.
• **- Space Complexity: $O(N \cdot L)$ auxiliary space to store nodes across the alphabet alphabet-branch array ($26$ size).