Untitled

/*
    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]; // an array of trienodes
    bool isterminal;
    trienode(char ch){
        data=ch;
        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');
    }

    /** Inserts a word into the trie. */
    void insertdriver(trienode* root, string str)
    {
        if(str.length()==0){  //base case
            root->isterminal=true;
            return;
        }
        trienode* child;
        int index=str[0]-'a';

        if(root->children[index]!=NULL){ // this character already exists in the children of root .. proceed
            child=root->children[index];
        }else{
            child =new trienode(str[0]);  // this character isnt present in children of root. create it and then 
            root->children[index]=child;  // proceed
        }
        insertdriver(child,str.substr(1)); //recursion
    }   
    void insert(string word) {
        insertdriver(root,word);
    }

    /** Returns if the word is in the trie. */
    bool searchdriver(trienode* root,string str){
        if(str.length()==0) return root->isterminal;
        
        int index=str[0]-'a';
        if(root->children[index]==NULL) return false;
        return searchdriver(root->children[index],str.substr(1));
    }
    bool search(string word) {
        return searchdriver(root,word);
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool presdriver(trienode* root,string str){
        if(str.length()==0) return true;
        
        int index=str[0]-'a';
        if(root->children[index]==NULL) return false;
        return presdriver(root->children[index],str.substr(1));
    }
    bool startsWith(string prefix) {
        return presdriver(root,prefix);
    }
};