#include <iostream>
#include <string>
#include <cstdlib>
#include <conio.h>
#include <time.h>

using namespace std;
const int nr_kerk=1000000;
struct peme_nyje {
          char info;
         peme_nyje *majte;
         peme_nyje *djathte;
       };

peme_nyje *rrenja;
bool ugjet;
char celes;

clock_t startTime, stopTime=0;

void start(){
	startTime=clock();
}

void stop(){
	stopTime=clock();
}

clock_t interval(){
	return stopTime-startTime;
}

void insert (char vl, peme_nyje * &p)
{
     if (p==NULL){
       p= new peme_nyje;
       p->info=vl;
       p->majte=NULL;
       p->djathte=NULL;
       }
     else
       if (vl<=p->info)
         insert(vl,p->majte);
       else
         insert(vl,p->djathte);
     }

void pararendore(peme_nyje *t )
  {
   if (t !=NULL)

   {
     cout<< t->info ;
     pararendore( t->majte );
     pararendore( t->djathte );
  }
}

 void nderrendore(peme_nyje *t)
  {
    if (t !=NULL)
    {
       nderrendore( t->majte );
       cout<< t->info;
       nderrendore( t->djathte );
     }
}

 void pasrendore(peme_nyje *t)
  {
    if (t !=NULL)
    {
       pasrendore( t->majte );
       pasrendore( t->djathte );
       cout<< t->info;
     }
}


  void kerko(char celes, bool &ugjet,peme_nyje *t )
  {
  if ((t!=NULL) && (!ugjet))
  {
    if (celes == t->info)
      ugjet = true;
    else
      if (celes < t->info)
         kerko(celes, ugjet, t->majte);
      else
         kerko(celes, ugjet, t->djathte);
    }
  }


int numero_nyje( peme_nyje *&t)
{

 if ( t==NULL)
    return 0;
  else
   return numero_nyje(t->majte)+1+numero_nyje(t->djathte);
}

int numero_gjethe(peme_nyje *&t)
{

 if (t==NULL)
    return 0;
  else
    if ((t->majte==NULL) && (t->djathte==NULL))
      return 1;
    else
     return numero_gjethe(t->majte)+numero_gjethe(t->djathte);
}

    int lartesia(peme_nyje *p)
    {
        int l,majte_l,djathte_l;
        l=majte_l=djathte_l=0;
        if(p->majte!=NULL)
            majte_l=(1+lartesia(p->majte));
        else if(p->djathte!=NULL)
                djathte_l=(1+lartesia(p->djathte));
        l=majte_l>djathte_l?majte_l:djathte_l;
        return(l);
    }


int main(){

    char vl;
    int zgjedhje;
    int i=0;
    double t1, t2;
    char c[] = "DAETUIOPAQ";//var qe mban sekuencen e karaktereve ku secili karakter perben vleren e nje kulmi te caktuar

    cout<<"\n\nKrijimi i nje peme binare..................\n";
    rrenja=NULL;
//  insert('A',rrenja);
//  insert('C',rrenja);
//  insert('B',rrenja);
//  insert('G',rrenja);
//  insert('E',rrenja);
    do
    {
        cout<<"\n 1.  Inserto nyje";
        cout<<"\n 2.  Afisho lartesine e pemes";
        cout<<"\n 3.  Bredhje ParaRendore";
        cout<<"\n 4.  Bredhje NderRendore";
        cout<<"\n 5.  Bredhje PasRendore";
        cout<<"\n 6.  Afisho numrin e nyjeve";
        cout<<"\n 7.  Afisho numrin e gjetheve";
        cout<<"\n 8.  Kerko nje nyje";
        cout<<"\n 9. Dalje nga programi";
        cout<<"\n\n Jepni nje nga opsionet e mesiperme............_  ";
        cin>>zgjedhje;
        switch(zgjedhje)
            {
                case 1:
                    system("CLS");
                    while(c[i]!='\0')
                    {
                        vl=c[i];
                        i++;
                        insert(vl,rrenja);
                    }
                    break;
                case 2:
                    system("CLS");
                        cout<<"\n\n  Lartesia e pemes:= "<<lartesia(rrenja);
                        cout<<endl;
                        break;
                case 3:
                    system("CLS");
                        cout<<"\n\n Bredhje ParaRendore : \n\n\n\n\t\t";
                        pararendore(rrenja);
                        cout<<endl;
                        break;
                case 4:
                    system("CLS");
                        cout<<"\n\n Bredhje NderRendore  :\n\n\n\n\t\t";
                        nderrendore( rrenja );
                        cout<<endl;
                        break;
                case 5:
                    system("CLS");
                        cout<<"\n\n Bredhje PasRendore   :\n\n\n\n\t\t";
                        pasrendore(rrenja);
                        cout<<endl;
                        break;
                case 6:
                    system("CLS");
                        cout<<"Numri i nyjeve: \n";
                        cout<<numero_nyje(rrenja);
                        cout<<endl;
                        start();
  						for(int i=0; i<nr_kerk; i++){
  							numero_nyje(rrenja);
  						}
  						stop();
  						t1=interval()/double(10*nr_kerk);
  						cout<<"Koha: "<<t1;
                        cout<<endl;
                        break;
                case 7:
                    system("CLS");
                        cout<<"Numri i gjetheve: \n";
                        cout<<numero_gjethe(rrenja);
                        cout<<endl;
                        start();
  						for(int i=0; i<nr_kerk; i++){
  							numero_gjethe(rrenja);
  						}
  						stop();
  						t2=interval()/double(10*nr_kerk);
  						cout<<"Koha: "<<t2;
                        cout<<endl;
                        break;
                case 8:
                    system("CLS");
                        cout<<"Shkruani nyjen qe kerkoni (nje shkronje)";
                        ugjet = false;
                        cin>>celes;
                        kerko( celes, ugjet, rrenja);
                        if (ugjet)
                           cout<<celes<< " u gjet";
                        else
                           cout<<celes<< " nuk u gjet.";
                           cout<<endl;
                        break;
                 case 9:
                       exit(0);
                        break;
                default:
                        cout<<"\n\n Zgjedhje jo e sakte !!!!!!!!!!!!!!!!!!!!!";
                        cout<<endl;
                        break;
            }
    }while(zgjedhje!=9);



  return 0;


}