//
// 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;

  if (tree==NULL)
    return false;

  // If we find the string
  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
	    // FILL IN CODE HERE
    }
    else {                         // two children
	    // FILL IN CODE HERE
    }
    return true;
  }

  // Keep recursing
  else {
	  // FILL IN CODE HERE
  }
}