// Arup Guha
// 7/8/03
// Brief Descruption: The following binary tree class manages a simple
//                    binary search tree and allows for insertions,
//                    searches, deletions and an inorder traversal.

#include <iostream.h>

//A struct to store a single binary tree node.
struct bintreenode {
  int data;
  bintreenode *left;
  bintreenode *right;
};


class BinTree
{
  public:
    BinTree();
    BinTree(bintreenode* node);
    void insert(int val);
    void printout();
    bool search(int val);
    bool del(int val);
    int numChildren();
    int max();
    int maxLeft();

  private:
    bintreenode *root;
};

// Creates an empty binary tree.
BinTree::BinTree() {
  root = NULL;
}

// Creates a binary tree rooted at the input parameter node.
BinTree::BinTree(bintreenode* node) {
  root = node;
}

// Inserts a node storing val into the current object.
void BinTree::insert(int val) {

  // Create the node to insert.
  bintreenode* temp = new bintreenode;
  temp->data = val;
  temp->left = NULL;
  temp->right = NULL;

  // Empty tree insert case.
  if (root == NULL) {
    root = temp;
    return;
  }

  bool done = false;
  bintreenode *tmpptr;
  tmpptr = root;

  // Continue until node has been inserted.
  while (!done) {

    // Case of node to be inserted to the left.
    if (val < tmpptr->data) {
    
      // Recursive case of inserting into the left subtree.
      if (tmpptr->left != NULL) 
        tmpptr = tmpptr->left;

      // Insert the node.
      else {
        tmpptr->left = temp;
        done = true;
      }        
    }
    else {

      // Recursive case of inserting into the right subtree.
      if (tmpptr->right != NULL)
        tmpptr = tmpptr->right;

      // Insert the node.
      else { 
        tmpptr->right = temp;
        done = true;
      }
    }
  }
}

// Prints out all the values in the binary search tree in ascending order.
void BinTree::printout() {

  // Recursively prints out all values in the left subtree.
  if (root->left != NULL) {
    BinTree temp(root->left);
    temp.printout();
  }

  //Print out value stored at the root.
  cout << root->data << endl;

  // Recursively print out all values in the right subtree.
  if (root->right != NULL) {
    BinTree temp(root->right);
    temp.printout();
  }
}

// Returns true if val is stored in the current object, false otherwise.
bool BinTree::search(int val) {

  // No value can be in an empty tree.
  if (root == NULL)
    return false;

  // Value found at the root of the tree.
  if (root->data == val)
    return true;

  // Otherwise, search the appropriate subtree.
  else {
    if (val < root->data) {
      BinTree temp(root->left);
      return temp.search(val);
    }
    else {
      BinTree temp(root->right);
      return temp.search(val);
    }
  }
}

// If val is stored in the current object, it is deleted from the tree and
// true is returned. Otherwise, false is returned.
bool BinTree::del(int val) {

  // Take care of empty tree case.
  if (root == NULL)
    return false;

  // Take care of deletion of the root node.
  if (root->data == val) {

    int numChild = numChildren();

    // Deletes root node when it is the only node in the tree.
    if (numChild == 0) {
      bintreenode* temp = root;
      root = NULL;
      delete temp;
    }

    else if (numChild == 1) {

      // Changes the reference for root to the appropriate subtree and
      // deletes the old root node.
      bintreenode* temp = root;
      if (root->left == NULL) {
        root = root->right;
        delete temp;
      }
      else {
        root = root->left;
        delete temp;
      }
    }
    else {

      // Find the largest value on the left side of the tree and deletes
      // it. Then stores this value at the root.
      int val = maxLeft();
      del(val);
      root->data = val;
    }

    return true;
  }
  
  // Set up variables to traverse the tree looking for the node,
  // keeping track of the parent of the potential deleted node.
  bintreenode* cur; 
  bintreenode* parent = root;
  bool direction;

  // Initialize the cur and direction variables.
  if (val < root->data) {
    direction = false;
    cur = root->left;
  }
  else {
    direction = true;
    cur = root->right;
  }

  // Continue while the node isn't found or it is determined to not be in
  // the tree.
  bool found = false;
  while (cur != NULL && !found) {

    // Found value to delete.
    if (val == cur->data) {
      found = true;
      BinTree temp(cur);
      int numChild = temp.numChildren();

      // Leaf node deletion; parent should be set to null.
      if (numChild == 0) {
        delete cur;
        if (direction)
          parent->right = NULL;
        else
          parent->left = NULL;        
      }

      // Deleting node with one child, parent link should be patched.
      else if (numChild == 1) {

        // Check for appropriate case for patching parent link.
        if (cur->left == NULL) {
          if (direction)
            parent->right = cur->right;
          else
            parent->left = cur->right;
        }
        else {
          if (direction)
            parent->right = cur->left;
          else
            parent->left = cur->left;
        }
        delete cur; // Delete actual node.

      }
      else {

        // Find the largest value in the left subtree of the node to be
        // deleted and delete it. Then stores this value at the root.
        int val = temp.maxLeft();
        temp.del(val);
        cur->data = val;
      }
    }

    // Continue searching for the value to delete in the left subtree.
    else if (val < cur->data) {
      parent = cur;
      direction = false;
      cur = cur->left;
    }

    // Continue searching for the value to delete in the right subtree.
    else {
      parent = cur;
      direction = true;
      cur = cur->right;
    }
  }

  return found;
  
}

// Returns the number of children the node pointed to by temp has.
int BinTree::numChildren() {

   // Case that there is no node.
  if (root == NULL)
    return -1;

  // No children
  if (root->left == NULL && root->right == NULL)
    return 0;

  // Both children
  else if (root->left != NULL && root->right != NULL)
    return 2;
  else
    return 1;
}

// Returns the maximum value stored in the current object.
int BinTree::max() {
  
  if (root == NULL)
    return 0;
  else if (root->right == NULL)
    return root->data;
  else {
    BinTree temp(root->right);
    return temp.max();
  }
}

// Returns the maximum value stored in the left subtree of the current
// object.
int BinTree::maxLeft() {
  
  if (root == NULL)
    return 0;
  else if (root->left == NULL)
    return root->data;
  else {
    BinTree temp(root->left);
    return temp.max();
  }
}

void main() {

  // Create a tree and test out some of the methods.
  BinTree mine;
  mine.insert(10);
  mine.insert(5);
  mine.insert(3);
  mine.insert(20);
  mine.insert(15);
  mine.insert(12);
  mine.insert(17);
  mine.insert(25);
  mine.printout();
  cout << endl;
  mine.del(10);
  mine.printout();
  cout << endl;
  mine.del(15);
  mine.printout();

  if (!mine.search(10))
    cout << "Ten was not found." << endl;

  if (mine.search(17))
    cout << "But seventeen was found." << endl;
}