Log inSign up
mediumCoding NinjasNot Started

Implement Trie

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trie
Solve on Coding Ninjas
Lesson

Problem Statement

Implement a complete Trie data structure (often called Trie II) that supports the following 4 operations:

1. insert(word): Inserts string word into the Trie. 2. countWordsEqualTo(word): Returns how many times string word was inserted. 3. countWordsStartingWith(prefix): Returns how many words in the Trie have the given prefix. 4. erase(word): Erases one occurrence of string word from the Trie.

All operations must execute in O(word.length) time.

Example 1 · Example 1: Insert, Count, and Erase:

Input: insert("apple"), insert("apple"), insert("apps"), countWordsEqualTo("apple"), countWordsStartingWith("app"), erase("apple"), countWordsEqualTo("apple")
Output: [null, null, null, 2, 3, null, 1]
Explanation: After inserting "apple" twice and "apps" once: - Words equal to "apple" = 2 - Words starting with "app" = 3 ("apple", "apple", "apps") - After erasing one "apple", words equal to "apple" = 1. Trie State: (root, pref: 3) | a (pref: 3) | p (pref: 3) | p (pref: 3) / \ (pref: 2)l s (pref: 1, end: 1) | (pref: 2)e (end: 2)

Constraints:

  • 1 <= word.length, prefix.length <= 100
  • All words consist only of lowercase English letters (a - z).
  • At most 104 total operations will be called.
  • erase(word) is guaranteed to only be called if word exists in the Trie.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master Trie node augmentation with integer counters (countPrefix and countEndWith).
  • Implement safe in-place deletion (erase) in a Trie structure without breaking sibling branches.
  • Understand how augmented nodes enable O(L) prefix counting without searching subtrees.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Need exact word count frequency AND prefix count frequency.
  • Requires dynamic erase functionality without corrupting other words with shared prefixes.
  • All queries require strict O(L) time bounds.

Algorithmic Decision Tree:

  • Standard boolean isEnd is insufficient because duplicates can exist; use integer countEndWith.
  • To support countWordsStartingWith, every intermediate node must maintain countPrefix.
  • To erase, trace the path and decrement countPrefix on each node, finally decrementing countEndWith.

Connected Patterns:

Implement Trie (Prefix Tree)Map Sum PairsPrefix and Suffix Search

1. Hash Map Frequency Counter with Linear Prefix Scan

Intuition

Maintain unordered_map<string, int>. insert increments map[word]. erase decrements map[word]. countWordsEqualTo reads map[word]. countWordsStartingWith scans all entries checking entry.startsWith(prefix).

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Map stores string -> frequency count.
  2. Step 2: insert: map[word]++.
  3. Step 3: countWordsEqualTo: return map[word].
  4. Step 4: countWordsStartingWith: sum frequencies of all keys starting with prefix.
  5. Step 5: erase: decrement map[word], remove key if 0.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <unordered_map>
4using namespace std;
5
6class Trie {
7 unordered_map<string, int> freq;
8public:
9 Trie() {}
10
11 void insert(string &word) {
12 freq[word]++;
13 }
14
15 int countWordsEqualTo(string &word) {
16 return freq.count(word) ? freq[word] : 0;
17 }
18
19 int countWordsStartingWith(string &word) {
20 int count = 0;
21 int len = word.length();
22 for (const auto& [key, val] : freq) {
23 if (key.length() >= len && key.rfind(word, 0) == 0) {
24 count += val;
25 }
26 }
27 return count;
28 }
29
30 void erase(string &word) {
31 if (freq.count(word)) {
32 freq[word]--;
33 if (freq[word] == 0) freq.erase(word);
34 }
35 }
36};
37
38int main() {
39 Trie trie;
40 string w1 = "apple", w2 = "apps", pref = "app";
41 trie.insert(w1);
42 trie.insert(w1);
43 trie.insert(w2);
44 cout << "countWordsEqualTo('apple'): " << trie.countWordsEqualTo(w1) << endl;
45 cout << "countWordsStartingWith('app'): " << trie.countWordsStartingWith(pref) << endl;
46 trie.erase(w1);
47 cout << "after erase, countWordsEqualTo('apple'): " << trie.countWordsEqualTo(w1) << endl;
48 return 0;
49}

Time & Space Complexity

  • Time complexity: insert: O(L), countEqual: O(L), countPrefix: O(N * L), erase: O(L) — Prefix search requires iterating through all distinct words in the hash map.
  • Space complexity: O(N * L) — Stores words and their frequency counts.

Why Brute Force Doesn't Scale:

With 10,000 words and 10,000 operations, naive scan requires 108 operations.

Augmenting nodes with integer counters turns prefix queries into an instant O(L) pointer read.

2. Two Hash Maps (Exact and Prefix Cache)

Intuition

Maintain exactMap and prefixMap. When inserting word, increment prefixMap[prefix] for every prefix of length 1 to L. erase decrements all prefix counts.

When to apply: Fast lookup when memory is plentiful and words are short.

Algorithm

  1. Step 1: Map 1: exact word counts.
  2. Step 2: Map 2: prefix string counts.
  3. Step 3: insert: increment exactMap[word] and loop i from 1 to L incrementing prefixMap[word.substr(0, i)].
  4. Step 4: erase: decrement exactMap[word] and all prefix counts.
  5. Step 5: Querying either map runs in O(L) time.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <unordered_map>
4using namespace std;
5
6class Trie {
7 unordered_map<string, int> exactMap;
8 unordered_map<string, int> prefixMap;
9public:
10 Trie() {}
11
12 void insert(string &word) {
13 exactMap[word]++;
14 string pref = "";
15 for (char c : word) {
16 pref += c;
17 prefixMap[pref]++;
18 }
19 }
20
21 int countWordsEqualTo(string &word) {
22 return exactMap.count(word) ? exactMap[word] : 0;
23 }
24
25 int countWordsStartingWith(string &word) {
26 return prefixMap.count(word) ? prefixMap[word] : 0;
27 }
28
29 void erase(string &word) {
30 if (exactMap.count(word) && exactMap[word] > 0) {
31 exactMap[word]--;
32 string pref = "";
33 for (char c : word) {
34 pref += c;
35 prefixMap[pref]--;
36 }
37 }
38 }
39};
40
41int main() {
42 Trie trie;
43 string w1 = "apple", pref = "app";
44 trie.insert(w1);
45 cout << "countWordsStartingWith('app'): " << trie.countWordsStartingWith(pref) << endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: insert: O(L^2), countEqual: O(L), countPrefix: O(L), erase: O(L^2) — String slicing of all L prefixes takes O(L2) time on insert and erase.
  • Space complexity: O(N * L^2) — Stores all prefix substrings in hash map.

3. Augmented Trie with countPrefix & countEndWith

Intuition

Every TrieNode tracks two counters: countPrefix (incremented every time a word passes through this node) and countEndWith (incremented when a word terminates at this node). erase simply traces the word's path and decrements each counter. Both query methods walk the word in O(L) and read the counter.

When to apply: Standard production & interview optimal solution for Trie II.

Algorithm

  1. Step 1: Define TrieNode with children[26], countPrefix = 0, countEndWith = 0.
  2. Step 2: insert(word): walk from root. At each node, create child if missing, move to child, and increment curr.countPrefix++. Finally, curr.countEndWith++.
  3. Step 3: countWordsEqualTo(word): walk Trie. If any child is null, return 0. At end, return curr.countEndWith.
  4. Step 4: countWordsStartingWith(prefix): walk Trie. If any child is null, return 0. At end, return curr.countPrefix.
  5. Step 5: erase(word): walk Trie. Decrement curr.countPrefix-- on each node along path. Finally, decrement curr.countEndWith--.

Interactive Trace for Augmented Trie

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: insert('app')
Visual state
Values and pointers at this exact step
tree
Root
pref: 1
char 'a'
pref: 1
char 'p'
pref: 1
char 'p'*
pref: 1, end: 1

Node order shown; add connections to display explicit tree edges.

curr: p2
Check / comparison
Node 'p' at level 3: countPrefix = 1, countEndWith = 1
Decision / next transition
Word 'app' successfully inserted.
Why this step matters

Step 1: insert(app). Walk a -> p -> p. Increment countPrefix at each node to 1. At final p, set countEndWith = 1.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3using namespace std;
4
5struct TrieNode {
6 TrieNode* children[26];
7 int countPrefix;
8 int countEndWith;
9
10 TrieNode() : countPrefix(0), countEndWith(0) {
11 for (int i = 0; i < 26; i++) children[i] = nullptr;
12 }
13};
14
15class Trie {
16 TrieNode* root;
17public:
18 Trie() {
19 root = new TrieNode();
20 }
21
22 void insert(string &word) {
23 TrieNode* curr = root;
24 for (char c : word) {
25 int idx = c - 'a';
26 if (!curr->children[idx]) {
27 curr->children[idx] = new TrieNode();
28 }
29 curr = curr->children[idx];
30 curr->countPrefix++;
31 }
32 curr->countEndWith++;
33 }
34
35 int countWordsEqualTo(string &word) {
36 TrieNode* curr = root;
37 for (char c : word) {
38 int idx = c - 'a';
39 if (!curr->children[idx]) return 0;
40 curr = curr->children[idx];
41 }
42 return curr->countEndWith;
43 }
44
45 int countWordsStartingWith(string &word) {
46 TrieNode* curr = root;
47 for (char c : word) {
48 int idx = c - 'a';
49 if (!curr->children[idx]) return 0;
50 curr = curr->children[idx];
51 }
52 return curr->countPrefix;
53 }
54
55 void erase(string &word) {
56 TrieNode* curr = root;
57 for (char c : word) {
58 int idx = c - 'a';
59 if (!curr->children[idx]) return;
60 curr = curr->children[idx];
61 curr->countPrefix--;
62 }
63 curr->countEndWith--;
64 }
65};
66
67int main() {
68 Trie trie;
69 string w1 = "apple", w2 = "apps", pref = "app";
70 trie.insert(w1);
71 trie.insert(w1);
72 trie.insert(w2);
73 cout << "Optimal countWordsEqualTo('apple'): " << trie.countWordsEqualTo(w1) << endl;
74 cout << "Optimal countWordsStartingWith('app'): " << trie.countWordsStartingWith(pref) << endl;
75 trie.erase(w1);
76 cout << "After erase, countWordsEqualTo('apple'): " << trie.countWordsEqualTo(w1) << endl;
77 return 0;
78}

Time & Space Complexity

  • Time complexity: All operations: O(L) — Each operation performs exactly L pointer dereferences and integer arithmetic in O(1) time.
  • Space complexity: O(Total inserted characters * 26) — Nodes store 26 pointers and two integers.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Hash Map of String Frequenciesinsert: O(L), countEqual: O(L), countPrefix: O(N * L), erase: O(L)O(N * L)Store words and their counts in unordered_map<string, int>. For countWordsStartingWith, iterate all N entries.Full hash table iteration for prefix queries.
2.Better — Two Hash Maps (Exact and All Prefixes)insert: O(L^2), countEqual: O(L), countPrefix: O(L), erase: O(L^2)O(N * L^2)Maintain an exact word map and a prefix map containing counts of all L prefixes of each word.Generating all L prefixes as string keys in the prefix hash map.
3.Optimal — Augmented Trie with Prefix & End CountersOptimalAll 4 operations strictly O(L)O(Total characters * 26)Every TrieNode stores children[26], countPrefix, and countEndWith. Traverse characters directly in O(1) per step.None. Perfect gold-standard implementation.

Common Pitfalls & Crucial Edge Cases

Using boolean `isEnd` instead of integer `countEndWith`

Prevents tracking duplicate identical word insertions.

Forgetting to decrement `countPrefix` during `erase`

Causes prefix queries to report phantom words that were deleted.

Deallocating nodes during erase without checking sibling words

Can corrupt other valid words sharing the prefix.

Crucial Edge Cases to Validate:

  • Deleting the only word in the Trie — countPrefix and countEndWith cleanly return to 0.
  • Inserting identical words multiple times — Handled naturally by integer increments rather than booleans.
  • Querying prefixes that do not exist — Returns 0 safely on first null pointer encounter.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain clearly why boolean flags are replaced by integer counters to support duplicate words and frequency queries.
  2. Mention that in languages with manual memory management (C++), nodes with countPrefix == 0 can optionally be pruned/freed.
  3. Highlight that every single operation is strictly bounded by O(L) time regardless of total dictionary size.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does erase only decrement countPrefix and countEndWith rather than deleting node objects directly?

2.What is the time complexity of countWordsStartingWith(prefix)?

Back to DSA Sheet