// bintree.cc P. Conrad CISC220 06J 
// simple binary tree class


#include "bintree.h"

BinTree::BinTree(int theData)
{
  data = theData;
  left = right = NULL;
}


BinTree::BinTree(int theData, BinTree *theLeft, BinTree *theRight)
{
  data = theData;
  left = theLeft;
  right = theRight;
}

BinTree::BinTree(const BinTree & orig)
{
  deepCopy(orig);
}
  

BinTree & BinTree::operator =(const BinTree &right)
{
  if (this == &right)
    return *this;
  
  cleanup();
  deepCopy(right);

  return (*this);
}

BinTree::~BinTree()
{
  cleanup();
}


void BinTree::deepCopy(const BinTree &src)
{
  // the following line does shallow copy if = is not overloaded
  // for the type of whatever "data" is; if that isn't good enough,
  // we can overload the = operator to do deep copy.  (In this case,
  // data is just an int, so no worries).

  data = src.data; 

  if (src.left == NULL)
    left = NULL;
  else
    left = new BinTree(* (src.left)); // uses copy constructor

  // we could do the right the same way
  // instead, this shows how we could use the ternary operator
  // instead of an if/else.    The if/else is more straightforward,
  // so it is the way I'd recommend.  But you should be able to 
  // read the code below if you encounter it.  Note the use of
  // a pointer value as a true/false value here.

  right = (src.right) ? new BinTree(* (src.right)) : NULL;

}

void BinTree::cleanup()
{
  // if data were a pointer to some data on the heap, 
  // here, we would call delete on it.   If it were a "composed" object,
  // its destructor would get called automatically after our own
  // destructor, so we would not have to worry about it.
  
  // so all we have to clean up is the left and right subchild.
  // It turns out that we don't have to check for null pointers;
  // C++ automatically ignores a call to delete on a NULL pointer
  // (according to the man page, the same is true with malloc() in C)
  
  // the COOLEST part is that if right is a non-null pointer,
  // the destructor gets called recursively!

  delete right; 
  delete left;

}


void BinTree::preOrder(ostream & out) const
{
  out << data << " ";
  if (left)
    left->preOrder(out);
  if (right)
    right->preOrder(out);
}


void BinTree::inOrder(ostream & out) const
{
  if (left)
    left->inOrder(out);
  out << data << " ";
  if (right)
    right->inOrder(out);
}

void BinTree::postOrder(ostream & out) const
{
  if (left)
    left->postOrder(out);
  if (right)
    right->postOrder(out);
  out << data << " ";

}


// print is a special preorder traversal
// that includes () to denote empty subtrees

void BinTree::print(ostream & out) const
{
  out << "(" << data << " ";

  if (left)
    left->print(out);
  else
    out << "()";

  out << " ";

  if (right)
    right->print(out);
  else
    out << "()";

  out << ")";

}


void BinTree::dotPrint(ostream &out) const
{
  out << "testing";
}

void BinTree::dotPrintHelper(ostream &out) const
{
  out << "testing helper";
}


ostream & operator << (ostream & left, const BinTree & right)
{
  right.print(left);
  return left;
}