Implement a Trie data structure that supports these operations:
insert(word)to store a word in the Triesearch(word)to check whether the complete word existsstartsWith(prefix)to check whether any stored word begins with the given prefix
Only lowercase English letters are considered in this version, so each node can keep links for a to z.
Example 1
Input: insert("apple"), search("apple"), search("app"), startsWith("app"), insert("app"), search("app")
Output: true, false, true, true
Explanation: "apple" is stored first, so searching "apple" succeeds. Searching "app" fails at that moment because only the prefix exists. After inserting "app", the complete word also becomes present.
Example 2
Input: insert("cat"), insert("car"), search("cap"), startsWith("ca"), startsWith("do")
Output: false, true, false
Explanation: "cap" was never inserted, so full-word search fails. Prefix "ca" exists because both stored words begin with it, while "do" does not match any stored path.
Approach
The key observation is that Trie operations do not compare a full word with other full words. Instead, each character chooses the next child node. Because of that, the logic for insert, search, and startsWith becomes a simple character-by-character walk.
A small but very important detail makes the implementation correct: reaching the end of a path is not enough to say a word exists. The final node must also be marked as an end-of-word node. This is what helps the Trie distinguish between "app" as a complete word and "app" as only a prefix inside "apple".
Key Points
Every node usually stores an array of 26 child references for lowercase English letters.
A boolean flag such as
isEndis needed to mark that a complete word finishes at that node.search(word)andstartsWith(prefix)look similar, butsearch(word)must also check the end marker.Inserting the same word again does not break the Trie. The ending node simply remains marked.
Algorithm
Create a root node that does not store any character and acts only as the starting point.
For
insert(word), move through the Trie one character at a time. If the required child node does not exist, create it.After processing the last character of the word, mark the current node as an ending node so the Trie knows a complete word finishes there.
For
search(word), follow the same path character by character. If a needed child is missing, returnfalseimmediately.After the full word is consumed in
search(word), return whether the last node is marked as a word ending.For
startsWith(prefix), only check whether the full prefix path exists. No end marker check is needed here.
Dry Run
Trie Implementation and Operations Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class TrieNode {public: vector<TrieNode*> children; bool isEnd; TrieNode() { children.assign(26, nullptr); isEnd = false; }};class Solution {private: TrieNode* root; int getIndex(char ch) { return ch - 'a'; }public: Solution() { root = new TrieNode(); } /* Inserts a word into the Trie. */ void insert(string word) { TrieNode* current = root; for (char ch : word) { int index = getIndex(ch); // Create a new node when the current character path is missing. if (current->children[index] == nullptr) { current->children[index] = new TrieNode(); } current = current->children[index]; } // Mark the last node so this path is treated as a complete word. current->isEnd = true; } /* Checks whether a complete word exists in the Trie. */ bool search(string word) { TrieNode* current = root; for (char ch : word) { int index = getIndex(ch); // If the next character path is missing, the word is not present. if (current->children[index] == nullptr) { return false; } current = current->children[index]; } // A full word exists only if the last node is marked as an ending node. return current->isEnd; } /* Checks whether any stored word starts with the given prefix. */ bool startsWith(string prefix) { TrieNode* current = root; for (char ch : prefix) { int index = getIndex(ch); // Prefix matching fails as soon as one required path is missing. if (current->children[index] == nullptr) { return false; } current = current->children[index]; } return true; }};// Driver code startsint main() { Solution trie; trie.insert("apple"); cout << boolalpha; cout << trie.search("apple") << "\n"; cout << trie.search("app") << "\n"; cout << trie.startsWith("app") << "\n"; trie.insert("app"); cout << trie.search("app") << "\n"; return 0;}Complexity Analysis
Time Complexity: O(L) for insert, search, and startsWith, where L is the length of the given word or prefix, because each operation processes one character at a time.
Space Complexity: O(26 * N) in pointer capacity terms for N nodes in a fixed-array implementation, while one single operation may create up to O(L) new nodes in the worst case during insertion.
Interview follow-up Questions
The flag is needed because a path can exist as only a prefix. Without that marker, "app" and "apple" would look the same at the point where "app" ends.
Be the first to add a comment.