Trie

This data structure is used for searching (primary purpose).

Here, 2 variables are use isRoot and Trie array
isRoot is used for denoting that we reach at a end of one word.
Trie array to used to store the data, and search the word.

Eg. abc
In trie trie[0]->trie[1]->trie[2]->true
//highlighted is the base trie and true is value of chain trie (denots end of word)
Here all other values are false or null.
if search bac
trie[1] -> null (return false)
if search ab
trie[0]->trie[1]->false (isRoot = false)

class Trie {
    bool isRoot;
    Trie* leaves[26];
public:
    Trie() {
        isRoot = false;
        for (int i = 0; i < 26; i++) leaves[i] = {};
    }
    
    void insert(string word, int i = 0) {
        if (word.size() == i) {
            isRoot = true;
            return;
        }
        int idx = word[i] - 'a';
        if (leaves[idx] == NULL) leaves[idx] = new Trie();
        leaves[idx]->insert(word, i+1);
    }
    
    bool search(string word, int i = 0) {
        if (i == word.size()) return isRoot;
        int idx = word[i] - 'a';
        
        if (leaves[idx] == NULL) return false;
        return leaves[idx]->search(word, i+1);
    }
    
    bool startsWith(string prefix, int i = 0) {
        if (i == prefix.size()) return true;
        int idx = prefix[i] - 'a';
        if (leaves[idx] == NULL) return false;
        return leaves[idx]->startsWith(prefix, i+1);
    }
};

/**
 * 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);
 */