#include<iostream>
#include<conio.h>
//#include<process.h>
using namespace std;
int n=0,a[100];
struct tree_node{
 tree_node *st;
 tree_node *dr;
 int info;
} ;
class bst{
 tree_node *root;
 public:
 bst(){
  root=NULL;
 }
 int isempty(){
  return(root==NULL);
 }
 void insert(int item);
 void inordinetrav();
 void inordine(tree_node *);
 void postordinetrav();
 void postordine(tree_node *);
 void preordinetrav();
 void preordine(tree_node *);
 int adanc(int val);
 void descendenti(int val);
};
void bst::insert(int val){
 tree_node *p=new tree_node;
 tree_node *parent;
 n++;
 a[n]=val;
 p->info=val;
 p->st=NULL;
 p->dr=NULL;
 parent=NULL;
 if(isempty()){
  root=p;
 }
 else{
  tree_node *ptr;
  ptr=root;
  while(ptr!=NULL){
   parent=ptr;
   if(val>ptr->info)
    ptr=ptr->dr;
   else
    ptr=ptr->st;
  } 
  if(val<parent->info)
   parent->st=p;
  else
   parent->dr=p;
 }
}
int bst::adanc(int val){
 tree_node *parent;
 tree_node *p=new tree_node;
 p=root;
 int adancime=0;
 if(val==p->info) return 0;
 while(p!=NULL){
  adancime++;
  parent=p;
  if(val>p->info){
   p=p->dr;
  }
  else if(val<p->info){
   p=p->st;
  }
  if(val==p->info){
   return adancime;
  }
  
 } 
}
void bst::descendenti(int val){
 tree_node *parent;
 tree_node *p=new tree_node;
 p=root;
 int gasit=0;
 while(p!=NULL && gasit==0){
  parent=p;
  if(val>p->info){
   p=p->dr;
  }
  else if(val<p->info){
   p=p->st;
  }
  if(val==p->info){
   gasit=1;
   if(p->st==0 && p->dr==0)
    cout<<p->info<<" ";
  }
  
 } 
}
void bst::inordinetrav(){
 inordine(root);
}
void bst::inordine(tree_node *p){
 if(p!=NULL){
  inordine(p->st);
  cout<<" "<<p->info<<"    ";
  inordine(p->dr);
 }
}
void bst::postordinetrav(){
 postordine(root);
}
void bst::postordine(tree_node *p){
 if(p!=NULL){
  postordine(p->st);
  postordine(p->dr);
  cout<<" "<<p->info<<"    ";
 }
}
void bst::preordinetrav(){
 preordine(root);
}
void bst::preordine(tree_node *p){
 if(p!=NULL){
  cout<<" "<<p->info<<"    ";
  preordine(p->st);
  preordine(p->dr);
 }
}
void main(){
 int i;

 bst b;
 b.insert(52);
 b.insert(25);
 b.insert(50);
 b.insert(15);
 b.insert(40);
 b.insert(45);
 b.insert(20);
 b.insert(27);
 b.insert(60);
 b.insert(55);
 /*b.insert(26);
 b.insert(62);
 b.insert(61);
 b.insert(70);
 b.insert(65);
 b.insert(71);
 b.insert(63);
 b.insert(64);
 */
 cout<<"nr de noduri este "<<n;
 cout<<"\n\nparcurgerea in: \n\n";
 cout<<"inordine"<<endl;
 b.inordinetrav();
 cout<<endl<<"postordine"<<endl;
 b.postordinetrav();
 cout<<endl<<"preordine"<<endl;
 b.preordinetrav();


 
 cout<<"\n\nnodurile in ordinea introducerii \n";
 int adancmax=0;
 for(i=1;i<=n;i++){
  cout<<a[i]<<" ";
  if(b.adanc(a[i])>adancmax)
   adancmax=b.adanc(a[i]);
 }
 cout<<"\n\nadancimea maxima este "<<adancmax<<endl;
 cout<<"\nnodurile terminale sunt "<<endl;
 for(i=1;i<=n;i++)
  b.descendenti(a[i]);


 getch();
}