//
// Binary Tree ADT implementation
//

#ifndef __TREE
#define __TREE

#include "stack.h"

template <class T>
class TreeNode {
 public:
  T key;
  TreeNode *left, *right;
  TreeNode (T k, TreeNode *l, TreeNode *r)
    { key = k; left = l; right = r; }
};

template <class T>
class BTree {

 protected:
  TreeNode<T> *Root;

 public:
  // Constructors and Destructors
  BTree ();
  BTree (T& item);
  BTree (T& item, BTree* l, BTree* r);
  BTree (T& item, BTree& l, BTree& r);
  ~BTree ();

 private:
  // Recursive implementation for deallocating the internal tree structure
  bool Destroy (TreeNode<T>* ptr);
  // Recursive implementation for duplicating an internal tree structure
  TreeNode<T>* dup (TreeNode<T>* ptr);
  // Recursive implementation for height
  int height (TreeNode<T>* ptr);

  
 public:
  // Add / Delete functions for items or subtrees
  bool AddLeft (T& item);
  bool AddLeft (BTree* sl);
  bool DeleteLeft ();
  bool AddRight (T& item);
  bool AddRight (BTree* sr);
  bool DeleteRight ();

 public:
  // Public height function - return the tree height
  virtual int Height ();

 private:
  // Private recursive helpers for internal tree structure traversal
  void inorder (TreeNode<T>* ptr, void (*Visit) (T&, int), int d);
  void preorder (TreeNode<T>* ptr, void (*Visit) (T&, int), int d);
  void postorder (TreeNode<T>* ptr, void (*Visit) (T&, int), int d);

 public:
  // Recursive solutions for internal tree structure traversals
  void Inorder (void (*Visit) (T&, int)); 
  void Preorder (void (*Visit) (T&, int)); 
  void Postorder (void (*Visit) (T&, int)); 

  // Iterative solutions for internal tree structure traversals using a stack
  void iInorder (void (*Visit) (T&));
  void iPreorder (void (*Visit) (T&));
  void iPostorder (void (*Visit) (T&));

  // Recursive search of an item
  virtual bool Search (T& i) { return Search (Root, i); }

 private:
  bool Search (TreeNode<T>*, T&);

};


// Constructors and Destructors
template <class T> BTree<T>::BTree () 
{ 
  Root = NULL; 
}

template <class T> 
BTree<T>::BTree (T& item) 
{ 
  Root = new TreeNode<T> (item, NULL, NULL); 
}

template <class T> 
BTree<T>::BTree (T& item, BTree* l, BTree* r) 
{ 
  Root = new TreeNode<T> (item, l ? dup (l->Root) : NULL, 
		                r ? dup (r->Root) : NULL); 
}
 
template <class T> 
BTree<T>::BTree (T& item, BTree& l, BTree& r) 
{ 
  Root = new TreeNode<T> (item, dup (l.Root), dup (r.Root)); 
}

template <class T> 
BTree<T>::~BTree () 
{ 
  Destroy (Root); 
  Root = NULL; 
}

// Recursive implementation for deallocating the internal tree structure
template <class T> 
bool BTree<T>::Destroy (TreeNode<T>* ptr) 
{
  if (ptr != NULL)
    {
      Destroy (ptr->left);
      Destroy (ptr->right);
      delete ptr;
      return true;
    }
  return false;
}

// Recursive implementation for duplicating an internal tree structure
template<class T> 
TreeNode<T>* BTree<T>::dup (TreeNode<T>* ptr)
{
  TreeNode<T>* crt = NULL;
  if (ptr != NULL)
    crt = new TreeNode<T> (ptr->key, dup (ptr->left), dup (ptr->right));
  return crt;
}
  
template <class T> 
bool BTree<T>::AddLeft (T& item) 
{ 
  if (Root->left != NULL)
    return false;
  Root->left = new TreeNode<T> (item, NULL, NULL);
  return true;
}

template <class T> 
bool BTree<T>::AddLeft (BTree* sl) 
{ 
  if (Root->left != NULL)
    return false;
  Root->left = dup (sl->Root);
  return true;
}

template <class T> 
bool BTree<T>::DeleteLeft () 
{ 
  Destroy (sl->left);
  Root->left = NULL;
}

template <class T> 
bool BTree<T>::AddRight (T& item) 
{ 
  if (Root->right != NULL)
    return false;
  Root->right = new TreeNode<T> (item, NULL, NULL);
  return true;
}

template <class T> 
bool BTree<T>::AddRight (BTree* sr) 
{ 
  if (Root->right != NULL) 
    return false;
  Root->right = dup (sr->Root);
  return true;
}

template <class T> 
bool BTree<T>::DeleteRight () 
{ 
  Destroy (Root->right);
  Root->right = NULL;
}

template <class T> 
int BTree<T>::height (TreeNode<T>* ptr)
{
  if (ptr == NULL)
    return 0;
  int sd = height (ptr->right);
  int sl = height (ptr->left);
  return 1 + (sd > sl ? sd : sl);
}

template <class T> 
int BTree<T>::Height () 
{
  return height (Root); 
}

template <class T> 
void BTree<T>::inorder (TreeNode<T>* ptr, void (*Visit) (T&, int), int d)
{
  if (ptr != NULL)
    {
      inorder (ptr->left, Visit, d+1);
      Visit (ptr->key, d);
      inorder (ptr->right, Visit, d+1);
    }
}

template <class T> 
void BTree<T>::preorder (TreeNode<T>* ptr, void (*Visit) (T&, int), int d)
{
  if (ptr != NULL)
    {
      Visit (ptr->key, d);
      preorder (ptr->left, Visit, d+1);
      preorder (ptr->right, Visit, d+1);
    }
}

template <class T> 
void BTree<T>::postorder (TreeNode<T>* ptr, void (*Visit) (T&, int), int d)
{
  if (ptr != NULL)
    {
      postorder (ptr->left, Visit, d+1);
      postorder (ptr->right, Visit, d+1);
      Visit (ptr->key, d);
    }
}

// Recursive solutions for internal tree structure traversals
template <class T> 
void BTree<T>::Inorder (void (*Visit) (T&, int)) 
{ 
  inorder (Root, Visit, 0); 
}

template <class T> 
void BTree<T>::Preorder (void (*Visit) (T&, int)) 
{ 
  preorder (Root, Visit, 0); 
} 

template <class T> 
void BTree<T>::Postorder (void (*Visit) (T&, int)) 
{ 
  postorder (Root, Visit, 0); 
}

// Iterative solutions for internal tree structure traversals
// using stack
template <class T> 
void BTree<T>::iInorder (void (*Visit) (T&))
{ 
  bool Done = false;
  TreeNode<T>* crt = Root;
  Stack<TreeNode<T>*> st;
  
  while (Done != true)
    {
      if (crt != NULL)
	{
	  st.Push (crt);
	  crt = crt->left;
	}
      else if (!st.isEmpty ())
	{
	  st.Pop (crt);
	  Visit (crt->key);
	  crt = crt->right;
	}
      else Done = true;
    }
}

template <class T> 
void BTree<T>::iPreorder (void (*Visit) (T&))
{ 
  TreeNode<T>* crt;
  Stack<TreeNode<T>*> st;
  
  st.Push (Root);
  while (!st.isEmpty ())
    {
      st.Pop (crt);
      if (crt != NULL)
	{
	  Visit (crt->key);
	  st.Push (crt->right);
	  st.Push (crt->left);
	}
    }      
}

// HW
template <class T> 
void BTree<T>::iPostorder (void (*Visit) (T&))
{ 
  
}


template <class T>
bool BTree<T>::Search (TreeNode<T>* ptr, T& i)
{
  if (ptr == NULL)
    return false;
  if (i == ptr->key)
    return true;
  return Search (ptr->left, i) || Search (ptr->right, i);
}

#endif