/***********************************************************
  Author  : Yan Huang
  Date    : 03.25.07
  Synopsis: a skeleton of a binary search tree ADT
***********************************************************/

#include <iostream>
#include <cstddef>
#include <string>
#include <sstream>

using namespace std;

struct TreeNode {
	int item;
	TreeNode *left;
	TreeNode *right;
};

class Btree {
public:
	Btree();
	~Btree();

	void insert(int key);
        void deleteKey(int key){}; // To be implemented
	TreeNode *search(int key) const;
	void inorder() const;
	void preorder() const{}; // To be implemented
	void postorder() const{}; // To be implemented
	void euler() const{}; // To be implemented
	int  numNode() const{}; // To be implemented
	int height() const{}; // To be implemented
	void swap() const{}; // To be implemented
        void print() const;

private:
	void inorderTraverse(TreeNode *node) const;
	void insert(int key, TreeNode *node);
        void print(int level, TreeNode *node) const; 
	TreeNode *search(int key, TreeNode *node) const;
        void deleteTree(TreeNode *node);

	TreeNode *root;
};

Btree::Btree() {
    root = NULL;
}

Btree::~Btree() {
  deleteTree(root);
}


void Btree::inorder() const{
	inorderTraverse(root);
        cout << endl;
}

void Btree::print() const{
    print(0,root);
    cout << endl;
}


void Btree::insert(int key) {
	if(root != NULL) {
           insert(key, root);
        } else {
           root = new TreeNode;
	   root->item = key;
	   root->left = NULL;
	   root->right = NULL;
	}
}

void Btree::inorderTraverse(TreeNode *node) const{
	if(node!= NULL)
	{
		inorderTraverse(node->left);
		cout << node->item << " ";
		inorderTraverse(node->right);
	}
}

TreeNode *Btree::search(int key) const{
	return search(key, root);
}

void Btree::insert(int key, TreeNode *node) {
	bool done = false;

	while(!done) {
		if(key < node->item) {
			if(node->left != NULL){
			    node = node->left;
                        } else {
		            node->left = new TreeNode;
		            node->left->item = key;
		            node->left->left = NULL;
		            node->left->right = NULL;
		            done = true;
	                }
		} else if(key > node->item) {
			if(node->right != NULL){
				node = node->right;
                        } else {
				node->right = new TreeNode;
				node->right->item = key;
				node->right->left = NULL;
				node->right->right = NULL;
				done = true;
			}
		}
		else if(key == node->item)
			done = true;
	}
}

TreeNode *Btree::search(int key, TreeNode *node) const{

    if(node != NULL) {
        if(key == node->item) {
	    return node;
	} else if(key < node->item){
	      node = node->left;
        } else {
	      node = node->right;
        }
    } else {
        return NULL;
    }
}


void Btree::print(int level, TreeNode *node) const{
   if (node != NULL){
       for (int i=0; i < level; i++){
           cout << ".";
       }  
       cout << node->item << endl;
       print(level+1, node->left);
       print(level+1, node->right);
   } else {
       for (int i=0; i < level; i++){
           cout << ".";
       }  
       cout << "NULL" << endl;
       return;
   }
}

void Btree::deleteTree(TreeNode *node){

    if (node != NULL){
        deleteTree(node->left);
        deleteTree(node->right);
        delete node;
    }
 /* added on April 9*/
    root = NULL;
}

int main() {
	Btree myTree;
        int key;


        
       /*****************************************************************
         read a list of numbers from std and insert them into the tree  
        *****************************************************************/

        cout <<"-------------------------------------------------------------" << endl;
	cout << "Enter the a list of integers to be inserted into the tree: ";


        string line; getline(cin, line); istringstream in(line); 
 

         while(in>> key) {
            myTree.insert(key);
         }



       /******************************
	Display the tree you you created
	******************************/
        cout <<"-------------------------------------------------------------" << endl;
	cout << "The tree you created looks like this: " << endl;
	myTree.print();


       /******************************
        Test deletion 
        *****************************/
        cout <<"-------------------------------------------------------------" << endl;
        cout << "Please input a key to be deleted from the tree" << endl;
        cin >> key;
        myTree.deleteKey(key);
        cout << "The tree after deleting " << key << " looks like t this:" << endl;
        myTree.print();

       /******************************
         Test travesal of the tree
        *****************************/
        cout <<"-------------------------------------------------------------" << endl;
        cout << "Performing in-order traversal of the tree:" << endl;
        myTree.inorder();
        cout << "Performing pre-order traversal of the tree:" << endl;
        myTree.preorder(); // You will need to print the keys produced by an preorder traversal of the tree
        cout << "Performing post-order traversal of the tree:" << endl;
        myTree.postorder();
        cout << "Performing euler traversal of the tree:" << endl;
        myTree.euler();

       /******************************
         Counting
         ******************************/
        cout <<"-------------------------------------------------------------" << endl;
        cout << "The number of nodes in the tree is " << myTree.numNode() << endl;
        cout << "The height of the the tree is " << myTree.height() << endl;
   
       /****************************
         Swap the two children
         ****************************/
        cout <<"-------------------------------------------------------------" << endl;
        cout << "The tree before swapping looks like this:" << endl;
        myTree.print();
        myTree.swap();
        cout << "The tree after swapping  looks like this: " << endl;
        myTree.print();

 
        return 0;
}