//
// FILE: strings2r.cpp
// Author: Leo Reyzin
// Purpose: code to delete strings in a binary search tree
// (code to take in strings, and print them out
// in ascending or descending order, and
// search for them, as well as main, is in strings2.cpp).
// HW4 of CS112B1 Spring 2003
//

#include<iostream>
#include<string>
using namespace std;

struct TreeNode {
   // a tree node contains a string
   string s;
   TreeNode *left, *right;

 
   TreeNode() {left=right=NULL;}
   TreeNode(string newS, TreeNode * newleft, TreeNode * newright) 
               {s=newS; left=newleft; right=newright;}
};


// Deletes a node containing s from the tree.  Note that the root
// of the tree is passed in by reference, in case it changes
// Returns true unless s is not in the tree
bool TreeDelete(TreeNode * & tree, string s)
{

  TreeNode *newtree, *nodeToMoveUp, *parentOfNodeToMoveUp;

  if (tree==NULL)
    return false;

  if (tree->s==s) {
    if (tree->right==NULL) {        // at most one child, on the left
      newtree=tree->left;
      delete tree;
      tree=newtree;
    }
    else if (tree->left==NULL) {   // a child only on the right
      newtree=tree->right;
      delete tree;
      tree=newtree;
    }
    else {                         // two children
      parentOfNodeToMoveUp=tree;
      nodeToMoveUp = tree->left;
      while (nodeToMoveUp->right!=NULL) {  // Find the predecessor
	parentOfNodeToMoveUp = nodeToMoveUp;
        nodeToMoveUp=nodeToMoveUp->right;
      }
      
      if (parentOfNodeToMoveUp!=tree) {
        // These are done only of tree's predecessor is not its left child
	// Then we need to save the right subtree of the predecessor
	// in the left of its parent, and the left subtree of tree
	// in the left of the node to move up.
        parentOfNodeToMoveUp->right = nodeToMoveUp->left;
        nodeToMoveUp->left = tree->left;
      }
      // These are always done
      // We need to save the right subtree of the tree in the node
      // to move up
      nodeToMoveUp->right = tree->right;
      delete tree;
      tree=nodeToMoveUp;
    }
    return true;
  }

  if(s<tree->s)
    return TreeDelete(tree->left, s);

  return TreeDelete(tree->right, s);
}