Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in C++

Implement Trie (Prefix Tree)

Understand and implement a Trie data structure to efficiently store strings and perform prefix matching. This lesson guides you through building insert, search, and prefix search operations, sharpening your skills for coding interviews that involve string manipulation.

We'll cover the following...

Statement

Trie is a tree-like data structure used to store strings. The tries are also called prefix trees because they provide very efficient prefix-matching operations. Implement a trie data structure with three functions that perform the following tasks:

  • Insert (word): This inserts a word into the trie.

  • Search (word): This searches the given word in the trie and returns TRUE if the complete word is found (i.e., all characters match and the last node is marked as the end of a word). Otherwise, return FALSE.

  • Search prefix (prefix): This searches the given prefix in the trie and returns TRUE if the prefix path exists in the trie (i.e., all prefix characters match), regardless of whether the last node is marked as the end of a word. Otherwise, return FALSE.

Constraints:

  • 1≤1 \leq word.length, prefix.length ≤500\leq 500
  • The strings consist only of lowercase English letters.
  • At most, 10310^3 calls in total will be made to the functions.

Examples

The Insert function does not return anything. The Search and Search prefix functions return TRUE if the input is found in the trie. Otherwise, they will return FALSE.

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Implement Trie

1.

Given a trie with the words [bat, bag, make, broom, bait], what will be the output of the following query?

search('bait')
A.

TRUE

B.

FALSE

1 / 3

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Note: The game below is only for the Insert function.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4
5

Try it yourself

Implement your solution in Trie.cpp in the following coding playground. You will need the provided supporting code to implement your solution.

C++
usercode > Trie.cpp
#include "TrieNode.cpp"
class Trie {
    public:
        Trie(){
            // constructor
        }
        // inserting string in trie
        void Insert(string word){
            // write your code here
        }
        // searching for a string
        bool Search(string word){
            // Replace this placeholder return statement with your code
            return false;
        }
        // searching for a prefix
        bool SearchPrefix(string prefix){
            // Replace this placeholder return statement with your code
            return false;
        }
};
Implement Trie (Prefix Tree)