#include<iostream>
using namespace std;


struct node{
    char a;
    bool leaf;
    struct node *child[26];
}*root;

struct node* newNode(char c)
{
    struct node *temp = new node();
    temp->a = c;
    temp->leaf = 0;
    for(int i=0;i<26;i++)
        temp->child[i] = NULL;
    return temp;
}

void build_trie(string k, int len, struct node* head)
{
    struct node *curr = head;
    for(int i=0;i<len;i++)
    {

        if(curr->child[k[i]-'a']==NULL)
            curr->child[k[i]-'a'] = newNode(k[i]);

        curr = curr->child[k[i]-'a'];
    }

    curr->leaf =1;
}

void print_trie(struct node *head, char pr[], int num)
{
    for(int i=0;i<26;i++)
    {
        if(head->child[i]!=NULL)
        {
            //cout<<"Data: "<<head->child[i]->a;
            pr[num] = head->child[i]->a;
            num++;
            print_trie(head->child[i],pr,num);

            if(head->child[i]->leaf == 1)
            {   for(int i=0;i<num;i++)
                    cout<<pr[i]<<" ";
                cout<<"\n";
            }
            num--;

        }
    }
}

bool search_trie(struct node *head, string k)
{
    int len = k.size();
    bool b = 1;
    int start =0 ;
    while(b)
    {
        if(head->child[k[start]-'a']!=NULL)
        {
            if(start==len-1)
            {
                if(head->child[k[start]-'a']->leaf != 1)
                    b=0;
            }
            head = head->child[k[start]-'a'];
            start++;
        }
        else
            b=0;
        if(start==len)
            break;
    }
    return b;
}

int main()
{

    //string arr[4] = {'neha','gauti','kesp','keshav'};
    //string s="keshav";
    char p='0';
    root = newNode(p);
    char pr[100];
    //for(int i=0;i<4;i++)
    //{
        //int len= arr[i].size();
        //cout<<len;
        //build_trie(arr[i],len,root);
        build_trie("keshav",6,root);
        build_trie("kesh",4,root);
        build_trie("gauti",5,root);
        build_trie("neha",4,root);
    //}
    print_trie(root,pr,0);
    if(search_trie(root,"kesh"))
        cout<<"In trie";
    else
        cout<<"Not in trie";
}