All about Trie Data Structure

// trei is a data structure which has an array and a leaf 

// array points to the next tries and leaf 

// tells whether this word ends or not.

#include <bits/stdc++.h>

using namespace std;

 

class Node{

    public:

    Node* arr[26];

    bool leaf;

    Node(){

        for(int i=0;i<26;i++) arr[i] = NULL;

        leaf = false;

    }

};

//recursive functions:

void addHelper(Node* root, string &word, int idx){

    //base case:

    if(idx == word.size()){

        root->leaf = true;

        return;

    }

    // check if word[idx] exists:

    if(root->arr[word[idx] - 'a'] == NULL){

        root->arr[word[idx] - 'a'] = new Node();   //make new

        // cout << word[idx] << " ";

    }

    //and call for next idx:

    addHelper(root->arr[word[idx] - 'a'], word, idx+1);

    return;

}

void add(Node* root, string &word){

    addHelper(root, word, 0);

}

//find function:

bool findHelper(Node* root, string &word, int idx){

    if(idx >= word.size()) return root->leaf;

    // check if exists -> not -> false:

    if(root->arr[word[idx] - 'a'] == NULL) return false;

    

    //call for next idx:

    return findHelper(root->arr[word[idx] - 'a'], word, idx+1);

}

bool find(Node* root, string &word){

    return findHelper(root, word, 0);

}

// print a Trie:

void displayHelper(Node* root, string str){

    if(root->leaf){

        // end:-> add end char and take the string:

        // str += '\0';

        cout << str << endl;

        return;

    }

    // run a loop for all possible children:

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

        if(root->arr[i]){

            // str += i + 'a';

            string n = str;

            n += (i + 'a');

            displayHelper(root->arr[i], n); //call for next:

        }

    }

    return;

}

void display(Node* root){

    string str = "";

    displayHelper(root, str);    

}

int main(){

    cout << "Code is running" << endl;

    Node* root = new Node();

    vector<string> v = {"tejas", "suraj", "tushar", "shrey", "yash"};

    for(auto word: v) add(root, word);

    // add(root, v[0]);

    // for(auto w: v){

    //     find(root, w) ? cout << "Yes" << endl : cout << "No" << endl; 

    // }

    // string s = "texas";

    // cout << find(root, s);

    display(root);

    return 0;

}