Implement Trie II (Prefix Tree)

Implement Trie II (Prefix Tree)

What is this problem about?

The Implement Trie II coding problem is an extension of the standard Trie data structure. In addition to the basic insert, search, and startsWith methods, you need to track frequencies. Specifically, you must implement:

• countWordsEqualTo(word): Return how many times a word has been inserted.
• countWordsStartingWith(prefix): Return how many words have the given prefix.
• erase(word): Remove one instance of a word from the Trie.

Why is this asked in interviews?

Companies like Microsoft and DoorDash use this to test a candidate's ability to maintain state within a tree. It moves beyond simple existence checks to counting and deletion, which requires updating metadata at every node along a path. It evaluates your understanding of how to propagate changes through a hierarchical data structure.

Algorithmic pattern used

This follows the Trie interview pattern with Node Metadata.

1. Node Structure: Each node needs two counters:
   • count: Number of words that end at this node.
   • prefixCount: Number of words that pass through this node.
2. Insertion: Increment prefixCount for every node on the path. Increment count at the final node.
3. Deletion: Decrement prefixCount for every node on the path. Decrement count at the final node.
4. Counting: Simply return the precalculated values stored at the target node.

Example explanation

1. insert("apple"): All nodes along 'a'-'p'-'p'-'l'-'e' get prefixCount = 1. The 'e' node gets count = 1.
2. insert("apple"): Nodes get prefixCount = 2, 'e' gets count = 2.
3. countWordsEqualTo("apple"): Go to 'e' node, return count (2).
4. erase("apple"): Nodes get prefixCount = 1, 'e' gets count = 1.
5. countWordsStartingWith("app"): Go to second 'p' node, return prefixCount (1).

Common mistakes candidates make

• Ignoring Memory: In languages like C++, forgetting to delete nodes that no longer have any prefixCount (though simple decrementing is often enough for interview logic).
• Deletion Errors: Failing to check if a word actually exists before trying to erase it, which can lead to negative counters.
• Redundant Search: Re-implementing the path-walking logic for every method instead of using a helper function.

Interview preparation tip

Trie II is about Metadata Management. Whenever you insert or delete, think about the "trail" you leave behind. Every node on the path must be aware of the total number of words it supports.