A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:


	Trie() Initializes the trie object.
	void insert(String word) Inserts the string word into the trie.
	boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
	boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.


&nbsp;
Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True


&nbsp;
Constraints:


	1 &lt;= word.length, prefix.length &lt;= 2000
	word and prefix consist only of lowercase English letters.
	At most 3 * 104 calls in total will be made to insert, search, and startsWith.


class Node : 
    def __init__(self ):
        self.child = {} # to hold the nodes.
        self.end = False # to mark a node if it is the end node or not.

class Trie:
    
    def __init__(self):
        self.root = Node()

    def insert(self, word:str) -> None:
        # time compl len(word)
        
        sz = len(word) 
        temp = self.root # to hold the root node.
        
        for ind , i in enumerate( word ) :
            if i in temp.child.keys() : # if this curr char in the current node.
                temp = temp.child[i] #another node.
                
            else:
                temp.child[i] = Node()
                temp = temp.child[i]

                
            if ind  == sz - 1 :
                temp.end = True 
                
                

    def search(self, word: str) -> bool:
        
        temp = self.root 
        for i in word : 
            if i in temp.child.keys():
                temp = temp.child[i]
            else:
                return 0
            
        return temp.end == True  
         
    def startsWith(self, prefix: str) -> bool:
        temp  = self.root 
        for i in prefix :
            if i in temp.child.keys():
                temp = temp.child[i]
            else:
                return 0
        return 1 
class Trie {
    private class Node{
        char character;
        Node[] sub;
        Node(char c){
            this.character = c;
            sub = new Node[26];
        }
    }
    Node root;
    HashMap<String, Boolean> map;
    public Trie() {
        root = new Node('\0');
        map = new HashMap<>();
    }

    public void insert(String word) {
        Node temp = root;
        for(char c : word.toCharArray()){
            int index = c-'a';
            if(temp.sub[index] == null)
                temp.sub[index] = new Node(c);

            temp = temp.sub[index];
        }
        map.put(word, true);
    }

    public boolean search(String word) {
        return map.containsKey(word);
    }

    public boolean startsWith(String prefix) {
        Node temp = root;
        for(char c : prefix.toCharArray()){
            int index = c-'a';
            if(temp.sub[index] == null)
                return false;
            temp = temp.sub[index];
        }
        return true;
    }
}
class Trie {
public:
    struct tr {
        bool isword;
        vector<tr*> next;
        tr() {
            next.resize(26, NULL); // one pointer for each character
            isword = false;
        }
    };
    
    tr *root;
    Trie() {
        root = new tr();
    }
    
    void insert(string word) {
        tr *cur = root;
        
        for(auto c: word) {
			// if pointer to char doesn't exist create one
            if(cur->next[c-'a'] == NULL) {
                cur->next[c-'a'] = new tr();
            }
            cur = cur->next[c-'a'];
        }
        
		// set as end or valid word
        cur->isword = true;
    }
    
    bool search(string word) {
        tr *cur = root;
        
        for(auto c: word) {
			// if pointer to char doesn't exist then word is not present
            if(cur->next[c-'a'] == NULL) {
                return false;
            }
            
            cur = cur->next[c-'a'];
        }
        
		// check if it is prefix or a word
        if(cur->isword){
            return true;
        }
        return false;
    }
    
	// similar to search 
	// here we don't check if it is end or not
    bool startsWith(string prefix) {
        tr *cur = root;
        
        for(auto c: prefix) {
            if(cur->next[c-'a'] == NULL) {
                return false;
            }
            
            cur = cur->next[c-'a'];
        }

        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */
var Trie = function() {
    this.children = {};
    this.word = false;
};

/**
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    if (!word) {
        this.word = true;
        return null;
    }
    let head = word[0];
    let tail = word.substring(1);

    if (!this.children[head]) {
        this.children[head] = new Trie();
    }
    this.children[head].insert(tail);
};

/**
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype._search = function(word, method) {
    if (!word) {
        if (method === 'search') {
            return this.word;
        } else {
            return true;
        }
    }
    let head = word[0];
    let tail = word.substring(1);

    if (!this.children[head]) {
        return false;
    }

    return this.children[head][method](tail);
};

/**
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    return this._search(word, 'search');
};

/**
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
    return this._search(prefix, 'startsWith');
};

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */
Implement Trie (Prefix Tree)