#include <iostream>
using namespace std;

struct TreeNode {
   int data;
   TreeNode *left;
   TreeNode *right;
};




class BinaryTree  {
private:
   TreeNode *root;
   
public:
   BinaryTree() { root = NULL; };
   ~BinaryTree() { ClearTree(root); };

   TreeNode* NewNode(int data);
   TreeNode* NewNode(TreeNode* x);

   bool isEmpty() {return (root == NULL); };
   TreeNode *SearchTree(int data);
   int Insert(TreeNode *node);
   int Insert(int data);
   int Delete(int data);
   void PrintNode(TreeNode *T) { std::cout << T->data << std::endl; };
   void PrintTree(TreeNode *T);
   int numNodes(TreeNode *T);
   void inorder(TreeNode *T);
   
private:
   void ClearTree(TreeNode *T);
};






// Helper function that allocates a new node with the
//  given data and NULL left and right pointers. 
TreeNode* BinaryTree::NewNode(int data) {
   TreeNode* node = new TreeNode;
   node->data = data;
   node->left = NULL;
   node->right = NULL;
   return(node);
}


TreeNode* BinaryTree::NewNode(TreeNode* x) {
   TreeNode* node = new TreeNode;
   node->data = x->data;
   node->left = x->left;
   node->right = x->right;
   return(node);
}



void BinaryTree::ClearTree(TreeNode *T) {

   if(T==NULL) return;  // Nothing to clear
   if(T->left != NULL) ClearTree(T->left); // Clear left sub-tree
   if(T->right != NULL) ClearTree(T->right); // Clear right sub-tree
   delete T;    // Destroy this node
}






TreeNode* BinaryTree::SearchTree(int data)
{
   TreeNode *temp = root;

   while((temp != NULL) && (temp->data != data)) 
      data < temp->data ? temp = temp->left  : temp = temp->right; 

   if(temp == NULL) return temp;    // Search key not found
   else return(NewNode(temp));      // Found it so return a duplicate
}






int BinaryTree::Insert(TreeNode *node) {

    TreeNode *temp = root;
    TreeNode *back = NULL;

   while((temp != NULL) )  {   // Loop till temp falls out of the tree 
      back = temp;
      node->data < temp->data ? temp = temp->left : temp = temp->right; 
   }

 
    // Now attach the new node to the node that back points to 
    if(back == NULL) // Attach as root node in a new tree 
        root = node;
    else 
       node->data < back->data ? back->left = node : back->right = node;

   return(1);
}







int BinaryTree::Insert(int data) {

   TreeNode *newNode = NewNode(data);
   // Call other Insert() to do the actual insertion
    return(Insert(newNode));
}




//////// Note: Deleting data from BST is a complicated business :( ////////
int BinaryTree::Delete(int data) {

   TreeNode *temp = root;// Temporary node for iteration 
   TreeNode *parent;    // Parent of node to delete
   TreeNode *delNode;   // Node to delete
   TreeNode *back;      // Spare node for backup

   
   while((temp != NULL) && (temp->data != data)) {
      back = temp;
      data < temp->data ? temp = temp->left  : temp = temp->right; 
   }

   if(temp == NULL) { // Didn't find the one to delete
      std::cout << "Data not found. Nothing deleted.\n";
        return false;
   }
   else if(temp == root) { // Deleting the root 
      delNode = root;
      parent = NULL; 
   }
   else {
      delNode = temp;
      parent = back;
   }

   // Start deleting 
   // Case 1: Deleting node with no children or one child 
    if(delNode->right == NULL) {
       if(parent == NULL) {   // If deleting the root    
          root = delNode->left;
          delete delNode;
          return true;
       }
       else {
          if(parent->left == delNode) parent->left = delNode->left;
          else parent->right = delNode->left;
          delete delNode;
          return true;
       }
    }
    else  // There is at least one child 
    {
       if(delNode->left == NULL)    // Only 1 child and it is on the right
       {
          if(parent == NULL) {   // If deleting the root    
             root = delNode->right;
             delete delNode;
             return true;
          }
          else {
             if(parent->left == delNode) parent->left = delNode->right;
             else parent->right = delNode->right;
             delete delNode;
             return true;
          }
       }       
       else // Case 2: Deleting node with two children 
       {
          // Find the replacement value.  Locate the node  
          // containing the largest value smaller than the 
          // key of the node being deleted.                
          temp = delNode->left;
          back = delNode;
          while(temp->right != NULL) {
             back = temp;
             temp = temp->right;
          }
          // Copy the replacement value into the node to be deleted 
          delNode->data = temp->data;
          
          // Remove the replacement node from the tree 
          if(back == delNode) back->left = temp->left;
          else back->right = temp->left;
          delete temp;
          return true;
       }
    }
}



void BinaryTree::PrintTree(TreeNode *T)
{
 
   if(T != NULL) {
      PrintTree(T->left);
      PrintNode(T);
      PrintTree(T->right);
   }
}


int BinaryTree::numNodes(TreeNode *T) {

   if(T == NULL) return 0;

   int  size = 1;
   TreeNode *left = T->left;
   TreeNode *right = T->right;

   if (left != NULL) size += numNodes(left);
   if (right != NULL) size += numNodes(right);

   return size;
}




void BinaryTree::inorder(TreeNode *T) {

   if(T != NULL) {
      inorder (T->left);
      std::cout << T->data << std::endl;
      inorder (T->right);
   }

}