#include<iostream>
#include <string>
using namespace std;

struct SuffixTreeNode{
    char c;
    SuffixTreeNode* one;
    SuffixTreeNode* two;
    SuffixTreeNode* three;
    SuffixTreeNode* four;
    SuffixTreeNode(char c=0) : c(c), one(nullptr), two(nullptr), three(nullptr), four(nullptr) { }
};

SuffixTreeNode* Insert(SuffixTreeNode* root,char ch){
    if (! root){
        root=new SuffixTreeNode(ch);
    }
    else if(ch=='a'){
        root->one=Insert(root->one,ch);
    }
    else if(ch=='c'){
        root->two=Insert(root->two,ch);
    }
    else if(ch=='g'){
        root->three=Insert(root->three,ch);
    }
    else if(ch=='t') {
        root->four=Insert(root->four,ch);
    }

    return root;
}

bool Search(SuffixTreeNode* root, int data){
	cout << (char)data<<"=="<<root->c<<"?"<<endl; 
    if(!root) return false;
    else if (root->c==data) return true;
    else if (data=='a')return Search(root->one,data);
    else if (data=='c')return Search(root->two,data);
    else if (data=='g')return Search(root->three,data);
    else return Search(root->four,data);
}


void Print(SuffixTreeNode* root, int x=0){
	for (int i=0; i<x; i++) cout<<" ";
    if(!root) cout <<"X"<<endl; 
    else {
    	cout << root->c <<endl; 
        Print (root->one, x+2);
    	Print(root->two,x+2);
    	Print(root->three,x+2);
    	Print(root->four,x+2);
    }
}

int main(){
    SuffixTreeNode* root=nullptr;
    char str;
    root=Insert(root,'a');
    root=Insert(root,'c');
    root=Insert(root,'c');
    root=Insert(root,'t');
    root=Insert(root,'a');
    root=Insert(root,'g');
    cout<<"Enter character to be searched\n";
    cin>>str;

    cout << "Searching "<<str<<" in:"<<endl;
    Print (root); 
    if(Search(root,str)) 
       cout<<"Found\n";
    else cout<<"Not found\n";
}