#include<iostream>
#include<string>
#include<vector>

using namespace std;

struct treeNode {
                 int item;
                 treeNode* LChildPtr;
                 treeNode* RChildPtr;
                 };

typedef treeNode* ptrType;

class BT
{
  public:
  // Constructors

  BT();  // Default constructor.
  
  void SetRootData (int newItem);  // puts newItem at the root, creating it if necessary;
  void AttachLeft (int newItem, bool& success); // puts newItem in the left child, creating it if necessary;
  void AttachRight (int newItem, bool& success); // puts newItem in the right child, creating it if necessary;
  void AttachLeftSubtree( BT & LeftTree, bool & success); // attaches LeftTree to Root's LChildPtr
  void AttachRightSubtree( BT & LeftTree, bool & success) ;// Attaches RightTree to Root's RChildPtr

  void PrintPreOrder();
  void PrintInOrder();
  void PrintPostOrder();

  protected:
   
  void copyTree (ptrType TreePtr, ptrType& NewTreePtr ) const; // Copies the subtree rooted at ptrType 
                                                              // to NewTreePtr
  void PreOrder(ptrType tp); // Prints the nodes in PrePrder
  void InOrder(ptrType tp); // Prints the nodes using InOrder
  void PostOrder(ptrType tp); // Prints the nodes using PostOrder
 
private :

   ptrType Root; // The top of the tree
   
};

 BT::BT(): Root(NULL){}
 
  void BT::SetRootData (int newItem) {
    if (Root == NULL)  {
      Root= new treeNode;
      Root -> item= newItem;
      Root-> LChildPtr= NULL;
      Root -> RChildPtr= NULL;
     }
     else Root-> item= newItem;
 }  
  void BT::AttachLeft (int newItem, bool& success) {
    success= false; 
    if (Root != NULL) {
      if (Root -> LChildPtr == NULL ) { 
         Root -> LChildPtr= new treeNode;
         Root -> LChildPtr -> item= newItem;
         Root -> LChildPtr -> LChildPtr= NULL;
         Root -> LChildPtr -> RChildPtr= NULL; // it's a leaf 
        success= true;
      }
    }
  } 

  void BT::AttachRight (int newItem, bool& success) {
 success= false;
    if (Root != NULL) {
      if (Root -> RChildPtr == NULL ) { 
         Root -> RChildPtr= new treeNode;
         Root -> RChildPtr -> item= newItem;
         Root -> RChildPtr -> LChildPtr= NULL;
         Root -> RChildPtr -> RChildPtr= NULL; // it's a leaf
        success= true;
      }
    }

 }

void BT::AttachLeftSubtree( BT & LeftTree, bool & success) {

  if (Root == NULL) success= false;
  else if (Root -> LChildPtr != NULL) success= false;
  else success= true;

  if (success) {
    copyTree (LeftTree.Root, Root -> LChildPtr);
   }
}
   

void BT::AttachRightSubtree( BT & RightTree, bool & success) {

  if (Root == NULL) success= false; 
  else if (Root -> RChildPtr != NULL) success= false;
  else success= true;

  if (success) {
    copyTree (RightTree.Root, Root -> RChildPtr);
   }
}   

  void BT::PrintPreOrder() { PreOrder(Root); }
  void BT::PrintInOrder() { InOrder ( Root ); } 
  void BT::PrintPostOrder() {PostOrder (Root) ;}


void BT::copyTree (ptrType TreePtr, ptrType& NewTreePtr ) const {

    // preOrdertraversal

   if ( TreePtr != NULL ) {
      NewTreePtr= new treeNode;
      NewTreePtr-> item = TreePtr-> item;
      NewTreePtr -> LChildPtr= NULL;
      NewTreePtr -> RChildPtr= NULL;

      copyTree( TreePtr -> LChildPtr, NewTreePtr -> LChildPtr);
      copyTree( TreePtr -> RChildPtr, NewTreePtr -> RChildPtr); 
   }

   else NewTreePtr= NULL;
}

  void BT::PreOrder(ptrType tp) {
     if ( tp != NULL ) {
        cout << tp -> item << " ";
        PreOrder( tp -> LChildPtr);
        PreOrder(tp -> RChildPtr);
     }
  }
  void BT::InOrder(ptrType tp) {
 if ( tp != NULL ) {
        InOrder( tp -> LChildPtr);
        cout << tp -> item << " ";
        InOrder(tp -> RChildPtr);  
     }
 }

  void BT::PostOrder(ptrType tp) {
   if ( tp != NULL ) {
        PostOrder( tp -> LChildPtr);
        PostOrder(tp -> RChildPtr);  
        cout << tp -> item <<  " ";
     }
}

int main () {

BT Left;
BT Right;

BT myTree;
bool s;

 Left.SetRootData( 5);
 Left.AttachLeft(10, s);
 Left.AttachRight(23, s);

 Right.SetRootData (7);
 Right.AttachLeft(10, s);
 Right.AttachRight(23, s);

 myTree.SetRootData(99);
 myTree.AttachLeftSubtree( Left, s);
 myTree.AttachRightSubtree( Right, s);

 cout << "Here's a Pre-order traversal " << endl;
    myTree.PrintPreOrder();  

    cout << endl;

  cout << "Here's an In-order traversal " << endl;
     myTree.PrintInOrder();

    cout << endl;
  cout << "Here's a Post-order traversal " << endl;
    myTree.PrintPostOrder();
   cout << endl;
}