Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Implement Trie

Hard
0/120
Average time to solve is 41m
225 upvotes
Asked in companies
UberInfosysTata Consultancy Services (TCS)

Problem statement

Implement Trie Data Structure to support these operations:

insert(word) - To insert a string "word" in Trie
search(word) - To check if string "word" is present in Trie or not.
startsWith(word) - To check if there is any string in the Trie that starts with the given prefix string "word".


Three type of queries denote these operations:

Type 1: To insert a string "word" in Trie.
1 word

Type 2: To check if the string "word" is present in Trie or not.
2 word

Type 3: To check if there is any string in the Trie that starts with the given prefix string "word".
3 word


Detailed explanation ( Input/output format, Notes, Images )
Input format :
The first line contains an Integer 'Q' which denotes the number of queries to be run. Then next 'Q' lines denote each query:

The first and only line of each query contains the type of query and a string "word" separated by a single space.
Output format :
For each query of Type 2 print the string "true" if string "word" is present in Trie or "false" otherwise.
For each query of Type 3 print the string "true" if there is any string in the Trie that starts with the given prefix string "word" or "false" otherwise.

Output for every query will be printed in a separate line.
Note:
You are not required to print the output explicitly, it has already been taken care of. Just implement the function.
Constraints :
1 <= Q <= 5*10^4
1 <= W <= 10

Where 'Q' is the number of queries, and 'W' is the length of the "word".
All input of "word" will consist of only lowercase letters a-z.
Sample Input 1 :
5
1 hello
1 help
2 help
3 hel
2 hel 
Sample Output 1 :
true
true
false
 Explanation to Sample Input 1 :
Query 1: "hello" is inserted
Query 2: "help" is inserted
Query 3: "true" is printed as "help" is present
Query 4: "true" is printed as "hello" and "help" is present having the prefix "hel"
Query 5: "false" is printed as "hel" is not present
Sample Input 2 :
10
1 aaaa
1 aaaaaa
1 bcd
2 aaaaa
3 aaaaa
3 bc
2 bc
1 bc
3 bcda
2 bc
Sample Output 2 :
false
true
true
false
false
true
 Explanation to Sample Input 2 :
Query 1: "aaaa" is inserted
Query 2: "aaaaaa" is inserted
Query 3: "bcd" is inserted
Query 4: "false" is printed as "aaaaa" is not present
Query 5: "true" is printed as "aaaaaa" is present having the prefix "aaaaa"
Query 6: "true" is printed as "bcd" is present having the prefix "bc"
Query 7: "false" is printed as "bc" is not present
Query 8: "bc" is inserted
Query 9: "false" is printed as no word is present having the prefix "bcda"
Query 10: "true" is printed as "bc" is present
Hint

Try to make a data structure similar to a tree which can support required operations.

 

Approaches (2)
Hashmap/Dictionary Approach

Firstly we have defined the node class of Trie having members:

  • child  - storing the address of child nodes (hashmap of character number and address of Trie Node)
  • isEnd - a bool variable for marking this node as an end of some word.

Then we have defined our Trie Class having members:

  • root - The root node for whole Trie, every word starts from this node.
  • insert(word) - To insert a string "word" in Trie
  • search(word) - To check if string "word" is present in Trie or not.
  • startsWith(word) - To check if there is any string in the Trie that starts with the given prefix string "word".

Definition of insert(word):

  • Initialize the current node with the root node of Trie.
  • Iterate over the word from left to right and if there is no node present for the next character of the word then create a new node and store it in child member of the previous character’s node.
  • Keep updating the current node to the corresponding node for the next character of the word.
  • Finally, when we reached the end of the word, mark the isEnd member of the current node to true as it will denote the word is present or not.

Definition of search(word):

  • Initialize the current node with the root node of Trie.
  • Iterate over the word from left to right and if there is no node present for the next character of the word then return false as the word is not present in the Trie.
  • Keep updating the current node to the corresponding node for the next character of the word.
  • Finally, when we reached the end of the word, return the isEnd bool variable of the current node as it will denote the word is present or not.

Definition of startsWith(word):

  • Initialize the current node with the root node of Trie.
  • Iterate over the word from left to right and if there is no node present for the next character of the word then return false as the no word is present in the Trie with this word as a Prefix.
  • Keep updating the current node to the corresponding node for the next character of the word.
  • Finally, when we reached the end of the word, return true as some word must be present in the Trie as we are able to cover the whole prefix word.
Time Complexity

O(N*W) (insert - O(W), search - O(W), startsWith - O(W))

where N is the number of queries and W is the average length of words.

For all the operations we are iterating over the word and checking in hashmap for the next character of the word so that’s an O(1) operation on average so Overall Time Complexity for insert, search, startsWith is O(W).

Space Complexity

O(N*W) where N is the number of words inserted and W is the average length of words.

As we are making nodes of each character of a node so at max we can have all unique sequence of the words. This hashmap approach of storing child is more space-efficient than an array for storing child as we will only store the address for the nodes present in the Trie.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Implement Trie
All tags
Sort by
Search icon

Interview problems

trie impl c/c++ using class

class Node 
{
    public:
    Node *links[26]={nullptr};
    bool flag=false;
    bool isPresent(char c)
    {
        return (links[c-'a']!=NULL);
    }
    void put(char c, Node * NewNode)
    {
          links[c-'a']=NewNode;
    }
    Node * newref(char c)
    {
        return links[c-'a'];
    }
    bool setEnd()
    {
        flag=true;
        
    }
    bool isend()
    {
        return flag;
    }
};

class Trie {
   
public:

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

    /** Inserts a word into the trie. */
    void insert(string word) {
        Node * cur=root;
            for(int i=0;i<word.length();i++)
            {
                if(!cur->isPresent(word[i]))
                {
                     cur->put(word[i], new Node()); 
                }
                cur=cur->newref(word[i]);
            }
            cur->setEnd();
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        Node *cur=root;
        for(int i=0;i<word.length();i++)
        {
            if(!cur->isPresent(word[i]))
            {
             return false;
            }
         cur=   cur->newref(word[i]);
        }
      return (cur->isend());
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Node *cur=root;
        for(int i=0;i<prefix.length();i++)
        {
            if(!cur->isPresent(prefix[i]))
            {
                return false;
            }
            cur=cur->newref(prefix[i]);
        }
        return true;
    }
};
37 views
0 replies
0 upvotes

Interview problems

C++ Solution

class Node{
    public:
       int flag = false;
       Node* links[26];
    
    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'];
    }
};

class Trie {
    Node* root;

public:

    /** Initialize your data structure here. */
    Trie() {
        root = new Node();
    }

    /** Inserts a word into the trie. */
    void insert(string word) {
        Node* node = root;

        for(int i = 0 ; i<word.size() ; i++){
            if(!node->containsKey(word[i])){
                Node* new_node  = new Node();
                node->put(word[i] , new_node);
            }

            node = node->get(word[i]);
        }

        node->flag = true;
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        Node* node = root;
        for(int i = 0 ; i<word.size() ; i++){
            if(!node->containsKey(word[i])){
                return false;
            }

            node = node->get(word[i]);
        }

        return node->flag;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Node* node = root;
        for(int i = 0 ; i<prefix.size() ; i++){
            if(!node->containsKey(prefix[i])){
                return false;
            }

            node = node->get(prefix[i]);
        }

        return true;
    }
};
305 views
0 replies
0 upvotes

Interview problems

Easy C++

Approach:

  • We implement a Trie data structure with the following functionalities: insertion of a word into the Trie, searching for a word in the Trie, and checking if there is any word in the Trie that starts with a given prefix.
  • We define a TrieNode class that represents each node in the Trie. Each TrieNode contains:
    • data: a character representing the character stored in the node.
    • children: an array of TrieNode pointers representing child nodes for each possible character ('a' to 'z').
    • isTerminal: a boolean flag indicating whether the current node marks the end of a word.
  • We implement the Trie class with the following methods:
    • insert: inserts a word into the Trie by recursively traversing the Trie and creating new nodes as necessary.
    • search: searches for a word in the Trie by recursively traversing the Trie and checking if the word exists.
    • startsWith: checks if there is any word in the Trie that starts with the given prefix by recursively traversing the Trie from the root and checking if all characters in the prefix are present.
  • For each operation, we start from the root of the Trie and traverse down the Trie according to the characters in the word or prefix being processed.
  • If a character node is not found during the traversal, we return false. Otherwise, for the search operation, we check if the current node marks the end of a word, and for the startsWith operation, we return true once the entire prefix has been traversed.
  • Time Complexity Analysis:
    • For insertion, searching, and prefix checking operations, the time complexity is O(L), where L is the length of the word or prefix being processed. This is because each operation involves traversing down the Trie, which takes O(L) time.
  • Space Complexity Analysis:
    • The space complexity is O(N * M), where N is the number of words inserted into the Trie, and M is the average length of the words. This is because the Trie stores each character of each word as a separate node, resulting in O(N * M) space usage.

 

 

 

Code : 

 

/*

    Your Trie object will be instantiated and called as such:

    Trie* obj = new Trie();

    obj->insert(word);

    bool check2 = obj->search(word);

    bool check3 = obj->startsWith(prefix);

 */

class TrieNode{

    public:

 

    char data;

    TrieNode* children[26];

    bool isTerminal;

 

    TrieNode(char ch){

        ch = data;

        for(int i=0; i<26; i++){

            children[i] = NULL;

        }

        isTerminal = false;

    }

};

 

class Trie {

 

public:

 

    TrieNode* root;

 

    /** Initialize your data structure here. */

    Trie() {

        root = new TrieNode('\0');

    }

 

    void insertUtil(TrieNode* root, string word){

        if(word.length()==0){

            root->isTerminal = true;

            return;

        }

 

        int index = word[0]-'a';

        TrieNode* child;

 

        if(root->children[index]!=NULL){

            child = root->children[index];

        }

        else{

            child = new TrieNode(word[0]);

            root->children[index] = child;

        }

 

        insertUtil(child, word.substr(1));

    }

    /** Inserts a word into the trie. */

    void insert(string word) {

        insertUtil(root, word);

    }

 

    bool searchUtil(TrieNode* root, string word){

        // base case

        if(word.length()==0){

            return root->isTerminal;

        }

 

        int index = word[0]-'a';

        TrieNode* child;

 

        if(root->children[index]!=NULL){

            child = root->children[index];

        }

        else{

            return false;

        }

 

        return searchUtil(child, word.substr(1));

    }

            

 

    /** Returns if the word is in the trie. */

    bool search(string word) {

        return searchUtil(root, word);

    }

 

    bool prefixUtil(TrieNode* root, string word){

            // base case

            if(word.length()==0){

                return true;

            }

 

            int index = word[0]-'a';

            TrieNode* child;

 

            if(root->children[index]!=NULL){

                child = root->children[index];

        }

            else{

                return false;

        }

 

        return prefixUtil(child, word.substr(1));

    }

 

    /** Returns if there is any word in the trie that starts with the given prefix. */

    bool startsWith(string prefix) {

        return prefixUtil(root, prefix);

    }

};

218 views
0 replies
2 upvotes

Interview problems

CPP SOLTUTION

/*

    Your Trie object will be instantiated and called as such:

    Trie* obj = new Trie();

    obj->insert(word);

    bool check2 = obj->search(word);

    bool check3 = obj->startsWith(prefix);

 */

 

class TrieNode{

    public:

        char data;

        TrieNode* children[26];

        bool isTerminal;

 

        TrieNode(char ch){

            data=ch;

            for(int i=0;i<26;i++){

                children[i]=NULL;

 

            }

            isTerminal=false;

        }

 

};

 

class Trie {

 

public:

 

    /** Initialize your data structure here. */

     TrieNode* root;

    Trie() {

        root=new TrieNode('\0');

    }

 

    /** Inserts a word into the trie. */

    void insertutil(TrieNode* root,string word){

        if(word.length()==0){

            root->isTerminal=true;

            return;

        }

        

        int index=word[0]-'a';

        TrieNode* child;

 

        if(root->children[index]!=NULL){

            child=root->children[index];

        }

        else{

            child=new TrieNode(word[0]);

            root->children[index]=child;

        }

 

        insertutil(child,word.substr(1));

 

    }

    void insert(string word) {

        insertutil(root,word);

    }

 

     bool searchutil(TrieNode* root,string word){

        if(word.length()==0){

            return root->isTerminal;

        }

 

        int index=word[0]-'a';

        TrieNode* child;

 

        if(root->children[index]!=NULL){

            child=root->children[index];

        }

        else{

            return false;

        }

 

        return searchutil(child,word.substr(1));

 

    }

 

    /** Returns if the word is in the trie. */

    bool search(string word) {

        return searchutil(root,word);

    }

 

    /** Returns if there is any word in the trie that starts with the given prefix. */

      bool prefixutil(TrieNode* root,string word){

        if(word.length()==0){

            return true;

        }

 

        int index=word[0]-'a';

        TrieNode* child;

 

        if(root->children[index]!=NULL){

            child=root->children[index];

        }

        else{

            return false;

        }

 

        return prefixutil(child,word.substr(1));

 

    }

 

    bool startsWith(string prefix) {

        return prefixutil(root, prefix);

    }

};

82 views
0 replies
1 upvote

Interview problems

Easy C++ Solution || All Test Case Passed

const int ALPHABETS = 26;

class trieNode{

    char ch;

 

    public:

        trieNode * children[ALPHABETS];

        bool isTerminal;

 

        trieNode(char ch) : ch(ch), isTerminal(false) {

            for(int i=0;i<ALPHABETS;++i) children[i] = nullptr;

        }

};

 

class Trie {

 

public:

    trieNode * root;

 

    /** Initialize your data structure here. */

    Trie() {

        root = new trieNode('\0');

    }

 

    void insertUtil(trieNode*, string);

    bool searchUtil(trieNode*, string);

    bool startsWithUtil(trieNode*, string);

 

    /** Inserts a word into the trie. */

    void insert(string word) {

        insertUtil(root, word);

    }

 

    /** Returns if the word is in the trie. */

    bool search(string word) {

        return searchUtil(root, word);

    }

 

    /** Returns if there is any word in the trie that starts with the given prefix. */

    bool startsWith(string prefix) {

        return startsWithUtil(root, prefix);

    }

};

 

void Trie :: insertUtil(trieNode* root, string str){

    if(str.length() == 0){

        root->isTerminal = true;

        return;

    }else{

        int index = str[0] - 'a';

        trieNode* child = nullptr;

 

        if(root->children[index] != nullptr) child = root->children[index];

        else{

            child = new trieNode(str[0]);

            root->children[index] = child;

        }

 

        insertUtil(child, str.substr(1));

    }

}

 

bool Trie :: searchUtil(trieNode* root, string str){

    if(str.length() == 0) return root->isTerminal;

    else{

        int index = str[0] - 'a';

        trieNode* child = nullptr;

 

        if(root->children[index] != nullptr) child = root->children[index];

        else return false;

 

        return searchUtil(child, str.substr(1));

    }

}

 

bool Trie :: startsWithUtil(trieNode* root, string str){

    if(str.length() == 0) return true;

    else{

        int index = str[0] - 'a';

        trieNode * child = nullptr;

 

        if(root->children[index] != nullptr) child = root->children[index];

        else return false;

 

        return startsWithUtil(child, str.substr(1));

    }

}

100 views
0 replies
0 upvotes

Interview problems

C++ | Simple and Easy implementation

class Node {
public:
    Node *child[26];
    bool isTerminal;

    Node(){
        for(int i = 0; i < 26; i++)
            child[i] = NULL;
        
        isTerminal = false;
    }

};

class Trie {
public:
    Node *root;

    /** Initialize your data structure here. */
    Trie() {
        root = new Node();
    }

    /** Inserts a word into the trie. */
    void insert(string word) {
        Node *node = root;
        for(int i = 0; i < word.size(); i++){
            if(node -> child[word[i] - 'a'] == NULL){
                node -> child[word[i] - 'a'] = new Node();
            }
            node = node -> child[word[i] - 'a'];
        }
        node -> isTerminal = true;
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        Node *node = root;
        for(int i = 0; i < word.size(); i++){
            if(node -> child[word[i] - 'a'] == NULL)
                return false;
            node = node -> child[word[i] - 'a'];
        }
        return node -> isTerminal;

    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Node *node = root;
        for(int i = 0; i < prefix.size(); i++){
            if(node -> child[prefix[i] - 'a'] == NULL)
                return false;
            node = node -> child[prefix[i] - 'a'];
        }
        return true;
    }
};
119 views
0 replies
0 upvotes

Interview problems

Java | Easy To Understand

public class Trie {


    //Initialize your data structure here
    static Node root;
    Trie() {
        //Write your code here
        root = new Node();
    }


    //Inserts a word into the trie

    public static void insert(String word) {
        //Write your code here
        Node curr = root;
        int N = word.length();

        for(int i=0; i<N; i++) {
            int index = word.charAt(i) - 'a';
            if(curr.children[index] == null) {
                curr.children[index] = new Node();
            }
            curr = curr.children[index];
        }
        curr.isEnd = true;
    }


    //Returns if the word is in the trie

    public static boolean search(String word) {
        //Write your code here
        Node curr = root;
        int N = word.length();

        for(int i=0; i<N; i++) {
            int index = word.charAt(i) - 'a';
            if(curr.children[index] == null) {
                return false;
            }
            curr = curr.children[index];
        }

        if(curr.isEnd) return true;

        return false;
    }

    
    //Returns if there is any word in the trie that starts with the given prefix

    public static boolean startsWith(String word) {
        //Write your code here
        Node curr = root;
        int N = word.length();

        for(int i=0; i<N; i++) {
            int index = word.charAt(i) - 'a';
            if(curr.children[index] == null) {
                return false;
            }
            curr = curr.children[index];
        }

        return true;
    }
}

class Node {
    Node children[] = new Node[26];
    boolean isEnd;

    Node() {
        isEnd = false;
        for(int i=0; i<26; i++) {
            children[i] = null;
        }
    }
}
224 views
0 replies
0 upvotes

Interview problems

important question hai ---> XD

/*
    Your Trie object will be instantiated and called as such:
    Trie* obj = new Trie();
    obj->insert(word);
    bool check2 = obj->search(word);
    bool check3 = obj->startsWith(prefix);
 */

 struct Node
 {
     Node* links[26];
     bool flag = false;

     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 setEnd()
     {
         flag = true;
     }

     bool isEnd()
     {
         return flag;
     }
 };



class Trie {

    private:
    Node* root;
    public:

    /** Initialize your data structure here. */
    Trie() {
      root = new Node();
    }

    /** Inserts a word into the trie. */
    void insert(string word) {
       Node* node = root;
       for(int i = 0;i<word.size();i++)
       {
           if(!node->containsKey(word[i]))
           {
               node->put(word[i],new Node());
           }
           node = node->get(word[i]);
       }
       node->setEnd();
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
       Node* node = root;
       for(int i = 0;i<word.size();i++)
       {
           if(!node->containsKey(word[i]))
           {
               return false;
           }
           node = node->get(word[i]);
       }
        return node->isEnd();
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string word) {
        Node* node = root;
       for(int i = 0;i<word.size();i++)
       {
           if(!node->containsKey(word[i]))
           {
               return false;
           }
           node = node->get(word[i]);
       }
       return true;
    }
};
131 views
0 replies
0 upvotes

Interview problems

c++ solution

 

class trienode

{

    public:

    char data;

    trienode* children[26];

    bool istermianl;

    

    trienode(char ch)

    {

        data=ch;

        for(int i=0;i<26;i++)

        {

            children[i]=NULL;

        }

        istermianl=false;

    }

};

class Trie {

public:

trienode* root;

    /** Initialize your data structure here. */

    Trie() {

         root=new trienode('\0');

    }

    void insertutil(trienode* root,string word)

     {

         //base case

         if(word.length()==0)

         {

             root->istermianl=true;

             return;

         }

         

         int index=word[0]-'a';

         trienode* child;

         if(root->children[index]!=NULL)

         {

             child=root->children[index];

             

             

         }

         else

         {

             child=new trienode(word[0]);

             root->children[index]=child;

         }

         insertutil(child,word.substr(1));

     }

 

    /** Inserts a word into the trie. */

    void insert(string word) {        

             insertutil(root,word);    

             }

 

    /** Returns if the word is in the trie. */

     bool searchutil(trienode* root,string word)

     {

         if(word.length()==0)

         {

             return root->istermianl;

         }

         int index=word[0]-'a';

         trienode* child;

         if(root->children[index]!=NULL)

         {

             child=root->children[index];

         }

         else

         {

             return false;

         }

          return searchutil(child,word.substr(1));

     }

     

    bool search(string word) {

 

         return searchutil(root,word);

 

    }

    

 

    /** Returns if there is any word in the trie that starts with the given prefix. */

     bool searchprefix(trienode* root,string word)

     {

         if(word.length()==0)

         {

             return true;

         }

         int index=word[0]-'a';

         trienode* child;

         if(root->children[index]!=NULL)

         {

             child=root->children[index];

         }

         else

         {

             return false;

         }

          return searchprefix(child,word.substr(1));

     }

    bool startsWith(string prefix) {

        return searchprefix(root,prefix);

 

    }

};

370 views
0 replies
2 upvotes

Interview problems

C++ Solution

class TrieNode {

public:

char data;

TrieNode* children[26];

bool isTerminal;

// constructor

TrieNode(char ch) {

this->data = ch;

this->isTerminal = false;

 

for(int i=0; i<26; i++) {

this->children[i] = NULL;

}

}

};

 

class Trie {

// creation of root node

TrieNode* root;

public:

 

/** Initialize your data structure here. */

Trie() {

// Initialization of root node

root = new TrieNode('\0');

}

// function to insert node into the tries

void insertUtil(TrieNode* &root, string word) {

if(word.length() == 0) {

root->isTerminal = true;

return;

}

 

// Assumption : Word will be in CAPS

int index = word[0] - 'a';

TrieNode* child;

 

if(root->children[index] != NULL) {

// Character Present

child = root->children[index];

} else {

// Character Absent

child = new TrieNode(word[0]);

root->children[index] = child;

}

 

// Recursive calls

insertUtil(child, word.substr(1));

}

 

/** Inserts a word into the trie. */

void insert(string word) {

insertUtil(root, word);

}

 

// function to search in tries

bool searchUtil(TrieNode* root, string word) {

// Base case

if(word.length() == 0) {

return root->isTerminal;

}

 

// Finding index through mapping

int index = word[0] - 'a';

TrieNode* child;

 

if(root->children[index] != NULL) {

// Present

child = root->children[index];

} else {

// Absent

return false;

}

// Recursive calls

return searchUtil(child, word.substr(1));

}

/** Returns if the word is in the trie. */

bool search(string word) {

return searchUtil(root, word);

}

// function to search the prefix present or not in tries

bool prefixUtil(TrieNode* root, string word) {

// Base case

if(word.length() == 0) {

return true;

}

 

// Finding index through mapping

int index = word[0] - 'a';

TrieNode* child;

 

if(root->children[index] != NULL) {

// Present

child = root->children[index];

} else {

// Absent

return false;

}

// Recursive calls

return prefixUtil(child, word.substr(1));

}

/** Returns if there is any word in the trie that starts with the given prefix. */

bool startsWith(string prefix) {

return prefixUtil(root, prefix);

}

};

148 views
0 replies
0 upvotes
Full screen
Console