// File: Tree_ADT.cpp
// Binary Tree ADT implementation

#include <iostream>
#include <string>
#include <queue>
#include "Tree_ADT.h"

using namespace std;

// Constructor
template <typename treeEltType> BinaryTree<treeEltType>::BinaryTree()
{root=NULL;}

// Place Element into Tree
// Returns 1 if inserted, 0 if data already in tree
template <typename treeEltType>
	  int BinaryTree<treeEltType>::insertToTree(const treeEltType &data)
{TreeNode<treeEltType> *t=root,*parent;
 if (!t) { // Empty Tree
  root=new TreeNode<treeEltType>(data);
  return(1);
 }
 // Search for spot to put data
 while(1) {
  if (!t) { // Nothing Here...Do the Insertion; won't be true 1st time
   if (data<parent->info) parent->left=new TreeNode<treeEltType>(data);
   else parent->right=new TreeNode<treeEltType>(data);
   return(1);
  }
  if (t->info==data) return(0); // data already in Tree
  parent=t; // Set the trail pointer to the ancestor of where we're going
  if (data<t->info) t=t->left;
  else t=t->right;
 }
}

// Search for Element in Tree
// Assumes == is defined for treeEltType
// Returns Ptr to Elt if Found, NULL otherwise
template <typename treeEltType>
    treeEltType *BinaryTree<treeEltType>::treeSearch(const treeEltType &key)
{TreeNode<treeEltType> *t;
 for (t=root;t && t->info!=key;)
  if (key<t->info) t=t->left;
  else t=t->right;
 if (t) 
  return(&(t->info));
 return(NULL);
}

// Retrieve Element from Tree (leaving Tree Intact)
// Precondition: Item is in Tree
template <typename treeEltType>
   treeEltType BinaryTree<treeEltType>::retrieveFromTree(const treeEltType &key) 
{TreeNode<treeEltType> *t;
 for (t=root;t->info!=key;)
  if (key<t->info) t=t->left;
  else t=t->right;
 return(t->info);
}

// Remove an Element from the tree
// Pre: Element is in the Tree
template <typename treeEltType>
      void BinaryTree<treeEltType>::deleteFromTree(const treeEltType &data)
{TreeNode <treeEltType> *nodeWithData,*nodeToDelete,*t,*trailT=NULL;
 for (t=root;t->info!=data;) {
  trailT=t;
  if (data<t->info) t=t->left;
  else t=t->right;
 }
 nodeWithData=t;  // Hold onto the data Node
 if (!(nodeWithData->left) && !(nodeWithData->right)) {
  // No Subtree, node is leaf...Wipe it
  // Is it the root?
  if (nodeWithData==root)
   root=NULL;
  else if (trailT->right==nodeWithData) trailT->right=NULL;
  else trailT->left=NULL;
  nodeToDelete=nodeWithData;    // free this at the end
 }
 else if (!(nodeWithData->left)) {  // No left Subtree of Node to Delete
  if (!trailT) { // Node to delete is root and there is no left subtree
   nodeToDelete=root;
   root=root->right;
  }
  else {// Otherwise, move up the right subtree
   if (trailT->right==nodeWithData) trailT->right=nodeWithData->right;
   else trailT->left=nodeWithData->right;
   nodeToDelete=nodeWithData;
  }
 }
 else if (!(nodeWithData->right)) {  // No right Subtree of Node to Delete
  if (!trailT) { // Node to delete is root and there is no left subtree
   nodeToDelete=root;
   root=root->left;
  }
  else {// Otherwise, move up the right subtree
   if (trailT->right==nodeWithData) trailT->right=nodeWithData->left;
   else trailT->left=nodeWithData->left;
   nodeToDelete=nodeWithData;
  }
 } 
 else { // Node has two children
   // Go to rightmost node in left subtree; we know there's a right child...
  for (trailT=nodeWithData,t=nodeWithData->left;
                                        t->right!=NULL;trailT=t,t=t->right);
  // Want to copy data from node with 0 or 1 child to node with data to delete 
  // Place node data in NodeWithData
  nodeWithData->info=t->info;
   // Set the parent of rightmost node to point at rightmost's left child
   //   (We know it hasn't a right child. Also takes care if no left child.
  if (trailT==nodeWithData) 
   // we just went left; 
   //   there was no right child, so this is rightmost node in left subtree
   trailT->left=t->left;
  else // we did go right; 
   // rightmost node has no r. child, so point its parent at its l. child 
   trailT->right=t->left;
  nodeToDelete=t;
 }
 delete nodeToDelete;
}

// Need Helper to Recursively Print the Tree
template <typename treeEltType>
     void BinaryTree<treeEltType>::printInorder(TreeNode<treeEltType> *t) const
//void printTheTree(TreeNode *T)
{if (t) {
  printInorder(t->left);
  cout << t->info << endl;
  printInorder(t->right);
 }
}

// Display Tree using InOrder Traversal
template <typename treeEltType> void BinaryTree<treeEltType>::inorder() const
{printInorder(root);}

// Need Helper to Recursively Print the Tree
template <typename treeEltType>
   void BinaryTree<treeEltType>::printPreorder(TreeNode<treeEltType> *t) const
//void printTheTree(TreeNode *t)
{if (t) {
  cout << t->info << endl;
  printPreorder(t->left);
  printPreorder(t->right);
 }
}

// Display Tree using InOrder Traversal
template <typename treeEltType> void BinaryTree<treeEltType>::preorder() const
{printInorder(root);}

// Need Helper to Recursively Print the Tree
template <typename treeEltType>
  void BinaryTree<treeEltType>::printPostorder(TreeNode<treeEltType> *t) const
//void printTheTree(TreeNode *t)
{if (t) {
  printPostorder(t->left);
  printPostorder(t->right);
  cout << t->info << endl;
 }
}

// Display Tree using InOrder Traversal
template <typename treeEltType> void BinaryTree<treeEltType>::postorder() const
{printInorder(root);}

template <typename treeEltType> void BinaryTree<treeEltType>::treePrint() const
{treePrintHelper(root);}

template <typename treeEltType> void BinaryTree<treeEltType>::
                        treePrintHelper(TreeNode<treeEltType> *root) const
{queue<TreeNode<treeEltType> *> Q;
 // A dummy node to mark end of level
 TreeNode<treeEltType> *dummy=new  TreeNode<treeEltType>(-1);
 if (root) {
   cout << root->info << " " << endl;
   Q.push(root->left);
   Q.push(root->right);
   Q.push(dummy);
 }
 TreeNode<treeEltType> *t=root;
 while (!Q.empty()) {
  t=Q.front();
  Q.pop();
  if (t==dummy) {
   if (!Q.empty()) 
    Q.push(dummy);
   cout << endl;
  }
  else if (t) {
   cout << t->info << " ";
   Q.push(t->left);
   Q.push(t->right);
  } 
 }
}

template class BinaryTree<int>;