/*BTree5.cpp - same as BTree2b.cpp but has successor function */
#include<iostream>
using namespace std;

class BTree
{
public:
  int key;  //data in the node
  BTree *left;   // Pointer to the left subtree.
  BTree *right;  // Pointer to the right subtree.
  BTree *parent; // Pointer to the parent node
  BTree();
  ~BTree();
  void insert(int key);   //insert a new node at a leaf position with the given int data
  void insert(BTree* leaf);  //insert a  given leaf node into the tree
  BTree *search(int key); //return NULL if no node has given int value, or a pointer to the node that has the int value
  void destroy();         //clean up the whole tree
  const void preOrderPrint();   
  const void inOrderPrint();
  const void postOrderPrint();
  BTree* find_Max();
  BTree* find_Min();
  int countNodes();
  int countLeafNodes();
  int find_depth();
  BTree* successor(int); //Returns pointer to successor node of this node
  BTree* predecessor(int) ; //Returns pointer to predecessor node of this node
};


BTree::BTree(){
  left=NULL;
  right=NULL;
  parent=NULL;
}

void BTree::insert(int key){
  BTree* bt=new BTree;  //new node
  bt->key=key;      //assign key to new node
  insert(bt);
}



void BTree::insert( BTree* leaf){
  if(!(this->key)){
       key=leaf->key;
     }
     else if ( (this->key) >= (leaf->key) ){
       if((this->left != NULL)){
	 (this->left)->insert(leaf);
       }else{
	 this->left=leaf;
	 leaf->parent=this;
       }
     }
     else {
       if(this->right != NULL){
	 (this->right)->insert(leaf);
       }else{
	 this->right=leaf;
	 leaf->parent=this;
       }
     }
}



     
const void BTree::inOrderPrint(){
  if( (left==NULL) && (right==NULL) ){
    if(key){cout<<key<<" ";}
  }
  else {
    if(left)left->inOrderPrint();
    cout<<key<<" ";
    if(right)right->inOrderPrint();
  }
}


const void BTree::preOrderPrint(){
  if( (left==NULL) && (right==NULL) ){
    if(key){cout<<key<<" ";}
  }
  else{
    cout<<key<<" ";
    if(left)left->preOrderPrint();
    if(right)right->preOrderPrint();
  }
}

const void BTree::postOrderPrint(){
  if( (left==NULL) && (right==NULL) ){
    if(key){cout<<key<<" ";}
  }
  else{
    if(left)left->postOrderPrint();
    if(right)right->postOrderPrint();  
    cout<<key<<" ";
  }
}


BTree* BTree::search(int keyval){
  if(this->key==keyval){
    return this;
  }
  else if( (this->key) > keyval){ //search in left subtree
    if(this->left)
      return this->left->search(keyval);
    else return NULL;
  }else{
    if(this->right)
      return this->right->search(keyval);
    else return NULL;
  }
}



BTree* BTree::find_Max(){
  if(right == NULL){
    return this;
  }else{
    right->find_Max();
  }
}

BTree* BTree::find_Min(){
  if(left == NULL){
    return this;
  }else{
    left->find_Min();
  }
}

int BTree::countNodes(){
  int l, r;
  if((left==NULL)&&(right==NULL)){
    if(key)return 1; else return 0;
  }
  else{
    if(left)
      l=left->countNodes(); else l=0;
    if(right)
      r=right->countNodes(); else r=0;
    return 1+l+r;
  }
}

int BTree::countLeafNodes(){
  int c=0,l=0,r=0;
  if((left==NULL)&&(right==NULL)){
    if(key) c++;
  }else{
    if(left)
      l=left->countLeafNodes(); 
    if(right)
      r=right->countLeafNodes(); 
  }
  return c+l+r;
}

int BTree::find_depth(){ 
  if(this==NULL)
    return 0;
  else{
    int leftDepth=left->find_depth();
    int rightDepth=right->find_depth();
    if (leftDepth>=rightDepth)
      return 1+leftDepth;
    else
      return 1+rightDepth;
  }
}




/***********Algorithm-Cormen/Leiserson/Rivest/Stein*********

TREE-SUCCESSOR(x)
if(right[x] != NULL)
   return find_min(right[x]);
y=parent[x];
while ( y != NULL and x == right[y]){
    x=y;
    y=parent[x];
}
return y
***********************************************************/

BTree* BTree::successor(int val){
  BTree* np=this->search(val); 
  if(np){               //should be a node in the tree
    if(np->right){      //node has a right subtree
      return (np->right)->find_Min();
    }
    else{ //go up the tree till you find a node which is a left child
      BTree* y= np->parent;
      BTree* x= np;
      while( (y != NULL) && (y->right==x)){
	x=y;
	y=x->parent;
      }
      if(y==NULL)
	return np; //np is Maximum element in the tree
      else
	return y;
    }
  }
  else return NULL; //node with given int value is not in the tree
}

BTree* BTree::predecessor(int val){
  BTree* np=this->search(val); 
  if(np){               //should be a node in the tree
    if(np->left){      //node has a right subtree
      return (np->left)->find_Max();
    }
    else{ //go up the tree till you find a node which is a right child
      BTree* y= np->parent;
      BTree* x= np;
      while( (y != NULL) && (y->left==x)){
	x=y;
	y=x->parent;
      }
      if(y==NULL)
	return np; //np is Minimum element in the tree
      else
	return y;
    }
  }
  else return NULL; //node with given int value is not in the tree
}

int main(){
  BTree* bt=new BTree; 
  bt->insert(12);
  bt->insert(5);
  bt->insert(10);
  bt->insert(21);
  bt->insert(13);
  bt->insert(3);
  bt->insert(15);
  bt->insert(22);
  bt->insert(7);
  cout<<"in-order->\t";bt->inOrderPrint();cout<<endl;
  cout<<"pre-order->\t"; bt->preOrderPrint(); cout<<endl;
  cout<<"post-order->\t"; bt->postOrderPrint(); cout<<endl;
  cout<<endl;
  cout<<"Max Value->"<<bt->find_Max()->key<<endl;
  cout<<"Min Value->"<<bt->find_Min()->key<<endl;
  cout<<"# of Nodes->"<<bt->countNodes()<<endl;
  cout<<"# of Leaf Nodes->"<<bt->countLeafNodes()<<endl;
  cout<<"Depth of the tree->"<<bt->find_depth()<<endl;

  cout <<"Successor of  10->"<< bt->successor(10)->key<<endl;
  int m;

  while (1){
    cout<<"Successor/predecessor of which element do you need?\n";
    cin>>m;

    if(bt->search(m)){
      cout <<"Successor of "<<m<<"->"<< bt->successor(m)->key<<endl;
      cout <<"Predecessssor of "<<m<<"->"<< bt->predecessor(m)->key<<endl;
    }
    else
      cout<<"Node not Found\n";
  }

  /*
  while (1){
    cout<<"enter a value to serach\n";
    cin>>m;
    if(bt->search(m)){
      cout<<"Found\n";
    }else{
      cout<<"Not Found\n";
    }
  }
  */
}