//////////////////////////////////////////////////////////////////////////////////////////////
//                 CSE 428, Spring 2001, code for third exercise of HW #3                   //
//                                   File A3_code_tree.C                                    //
//////////////////////////////////////////////////////////////////////////////////////////////

const int NULL = 0;

#include <iostream>
using namespace std;

//////////////////////////////////////////////////////////////////////////////////////////////

class tree { //implementation of a binary tree (only the methods relevant for this exercise)

private:
   int node;
   tree* left;
   tree* right;

public:
   tree(int x)
   {
      node = x;
      left = NULL;
      right = NULL;
   }

   void insert_right(tree* t) //Insert a tree as right subtree. 
                              //The current right subtree should be empty
   {
       if (right != NULL) 
	 cout << "Warning: subtree not empty\n";
       else 
          right = t;
   }

   void insert_left(tree* t) //Insert a tree as left  subtree. 
                             //The current left subtree should be empty
   {
       if (left != NULL) 
	  cout << "Warning: subtree not empty\n";
       else 
          left = t;
   }
};

tree* construct_a_tree(int k) //Construct a tree of height k
{  
   tree* t = new tree(k);

   if (k<0)
      cout << "Error: Negative height! \n";
   else if (k==0)
      cout << "level 0 reached \n";
   else {
      t->insert_left(construct_a_tree(k-1));
      t->insert_right(construct_a_tree(k-1));
   }
   
   return t;
}
   
/////////////////////////////////////////////////////////////////////////////////////////////

int main()
{
   tree* t = construct_a_tree(3); //construct a tree of height 3 
   // ...
}

///////////////////////////////////////////////////////////////////////////////////////////////