#include "stdstuff.h"
#include "Tree.h"


// recursive purge method deletes all the nodes in the tree pointed to by subroot
void Tree::purge (TNode* subroot) {

  if (subroot == NULL) return; // nothing to purge
  purge (subroot -> left); // dispose of the left subtree
  purge (subroot -> right); // dispose of the right subtree
  delete subroot; // get rid of the root node

}


// destructor
Tree::~Tree () {

  purge (root);

}


// recursive search sub method
bool Tree::subSearch (TNode *subRoot, int data) const {

  if (subRoot == NULL) return false;  // value doesn't exist

  if (subRoot -> data == data) return true;

  if (subRoot -> data > data) {
    return subSearch (subRoot -> left, data);
  } else {
    return subSearch (subRoot -> right, data);
  }

}



// really should be iterative like the insert method (for the same reasons).
// an iterative version would look just like the insert method with the code
// that does the actual insertion removed (and with the return values
// interchanged)
bool Tree::search (int data) const {

  return subSearch (root, data);

}


// iterative insert used because, when there is a relatively straightforward
// iterative method, it will typically be more efficient than a recursive one.
bool Tree::insert (int data) {

  TNode *p = NULL, *c = root, *n;
  bool wentRight;

  while (c != NULL && c -> data != data) {
    if (data < c -> data) {
      p = c; c = c -> left;  wentRight = false;
    } else {
      p = c; c = c -> right; wentRight = true;
    }
  }

  if (c != NULL) return false;  // data exists

  n = new TNode (data, NULL, NULL);
  if (p == NULL) {
    root = n;
  } else  if (wentRight) {
    p -> right = n;
  } else {
    p -> left = n;
  }

  return true;

}


// removes the rightmost node of a non-NULL tree and returns its value
// throws invalid_argument exception if tree is empty
int Tree::removeRightmost (TNode* &subRoot) {

  TNode *c;
  int result;

  if (subRoot == NULL) {
    throw invalid_argument ("Tree::deleteRightmost - empty tree");
  }

  if (subRoot -> right == NULL) {
    // we've gone as far to the right as we can
    c = subRoot;
    subRoot = subRoot -> left; // may or may not be NULL (works in either case)
    result = c -> data;
    delete c;
    return result;
  }

  return removeRightmost (subRoot -> right);

}


// recursive remove method: note that it can change subRoot
bool Tree::subRemove (TNode* &subRoot, int data) {

  TNode *c;

  if (subRoot == NULL) return false;

  if (subRoot -> data == data) {
    if (subRoot -> left != NULL && subRoot -> right != NULL) {
      // two children
      subRoot -> data = removeRightmost (subRoot -> left);
    } else {
      c = subRoot;
      if (subRoot -> left == NULL) {
        // no children or just a right child
        subRoot = subRoot -> right;
      } else {
        // just a left child
        subRoot = subRoot -> left;
      }
      delete c;
    }
    return true;
  }
  if (data < subRoot -> data) {
    // go left
    return subRemove (subRoot -> left, data);
  }
  // go right
  return subRemove (subRoot -> right, data);

}


// removes the given value from the tree
// returns true on success and false on failure (value not there)
bool Tree::remove (int data) {

  return subRemove (root, data);

}


// recursive print helper method
void Tree::subPrint (TNode *subRoot) const {

  if (subRoot == NULL) return;

  subPrint (subRoot -> left);
  cout << subRoot -> data << endl;
  subPrint (subRoot -> right);

}


// prints contents of the tree in-order
void Tree::print () const {

  subPrint(root);

}


// recursive display helper method
void Tree::subDisplay (String2002 leftPreString, String2002 midPreString,
                       String2002 rightPreString, TNode *subRoot) const {

  String2002 valueString, blankString;
  ostringstream formatter(ostringstream::out);

  if (subRoot == NULL) {

    cout << midPreString << "NULL\n";

  } else {

    // we want valueString to contain the data value followed by a hyphen.
    // the following is ugly but does the job.
    formatter << (subRoot -> data) << "-" << ends;
    valueString = formatter.str();
    // blankString is to consists of all blanks and to have the same
    // length as valueString.  this approach is crude but portable.
    for (int i = 0; i < valueString.length(); i++) {
      blankString += ' ';
    }

    subDisplay (rightPreString + blankString + "| ",
                rightPreString + blankString + "|-",
                rightPreString + blankString + "  ", subRoot -> right);
    cout << midPreString <<  valueString << "|\n";
    subDisplay (leftPreString + blankString + "  ",
                leftPreString + blankString + "|-",
                leftPreString + blankString + "| ", subRoot -> left);

  }

}


// displays the tree in graphical format
void Tree::display () const {

  subDisplay ("", "", "", root);

}


// recursive getHeight helper method
int Tree::subGetHeight (TNode *subRoot) const {

  int leftHeight, rightHeight;

  if (subRoot == NULL) return 0;
  leftHeight = subGetHeight (subRoot -> left);
  rightHeight = subGetHeight (subRoot -> right);
  if (leftHeight > rightHeight) {
    // left subtree is higher
    return 1 + leftHeight;
  }
  // right subtree is higher
  return 1 + rightHeight;

}


// returns the height of the tree (length of longest branch)
int Tree::getHeight () const {

  return subGetHeight (root);

}


void Tree::subPrune (TNode* &subroot, int height) {

   if (subroot == NULL) return; // no pruning possible
   
   if (height == 0) {
     // must get rid of entire subtree

     // Note: You can replace the following 3 lines with: purge(subroot);
     subPrune (subroot -> left, 0);
     subPrune (subroot -> right, 0);
     delete subroot;

     subroot = NULL; // note call by reference
     return;
   }
 
   // subroot should remain - prune its subtrees to correct height
   subPrune (subroot -> left, height - 1);
   subPrune (subroot -> right, height - 1);

}


void Tree::prune (int height) {

  subPrune (root, height);

}


int Tree::subGetNumLeaves(TNode* subRoot) const {

   if (subRoot==NULL) return 0;

   if (subRoot->left==NULL && subRoot->right==NULL) return 1; // no children, so count it

   // not a leaf so answer is sum of leaves in left and right subtrees
   return subGetNumLeaves(subRoot->left) + subGetNumLeaves(subRoot->right);

}


int Tree::getNumLeaves() const {

   return subGetNumLeaves(root);

}