//Complete the functions for getHeight, postorder and preorder tree traversal in the btree class below and show execution screen shot,

//also comment the new functions

//typed

//c++

using namespace std;

#include

using namespace std;

//Node class

class Node{

int key;

Node* left;

Node* right;

public:

Node() //constructor

{ key = -1; left = NULL; right = NULL;}

void setKey(int item)

{ key = item;}

void setLeft(Node* lefty)

{ left = lefty;}

void setRight(Node* righty)

{ right = righty;}

int getKey()

{ return key;}

Node* getLeft()

{ return left;}

Node* getRight()

{ return right;}

}; //class Node

//tree class

class Tree{

Node* root;

public:

Tree(); //constructor

~Tree(); //destructor

Node* getRoot()

{ return root;}

void addNode(int key);

void inOrder(Node* n);

void preOrder(Node* n);

void postOrder(Node* n);

private:

void addNode(int key, Node* leaf); //overloaded constructor

void freeNode(Node* leaf); //destructor

};

//Constructor

Tree::Tree()

{ root = NULL;}

//Destructor

Tree::~Tree()

{ freeNode(root);}

void Tree::freeNode(Node* leaf)

{

if(leaf !=NULL)

{

freeNode(leaf->getLeft());

freeNode(leaf->getRight());

delete leaf;

}

}//freeNode

//Add node

void Tree::addNode(int key)

{

if(root == NULL) //if empty tree

{

cout << "add a root node: " << key << endl;

Node* temp = new Node();

temp ->setKey(key);

root = temp;

}

else

{

addNode(key, root);

cout << "add new node: "<< key << endl;

}

}//addNode

void Tree::addNode(int key, Node* parent) //overloaded function

{

//if key < value at parent go left

if(key < parent->getKey())

{

if(parent -> getLeft() == NULL) //if left is empty

{

Node* n = new Node(); //create new node

n->setKey(key); //store it's key value

parent->setLeft(n); //have parent's left point to this node

}

else //if parent already has a left child

{

addNode(key, parent->getLeft()); //do the function again with this node as the parent

}

}

//if key >= value at parent go right

else

{

if(parent->getRight() == NULL) //if right child is empty

{

Node* n = new Node(); //create new node

n->setKey(key); //store it's key value

parent->setRight(n); //have parent's right point to this node

}

else //if parent has a right child

{

addNode(key, parent->getRight());

}

}

}//addNode

void Tree::inOrder(Node* n)

{

if(n) //keep going as long as there is a node available

{

inOrder(n->getLeft()); //grab key of left child

cout << n->getKey()<<" "; //print parent key

inOrder(n->getRight());//grab key of right child

}

}

int main() {

Tree* tree = new Tree();

tree->addNode(30);

tree->addNode(10);

tree->addNode(70);

tree->addNode(20);

tree->addNode(40);

tree->addNode(5);

tree->addNode(50);

tree->addNode(10);

cout<< " Tree height: " <getHeight(tree->getRoot()) << endl;

cout << "In order traversal" << endl;

tree->inOrder(tree->getRoot());

cout << endl;

cout << "Pre order traversal" << endl;

tree->preOrder(tree->getRoot());

cout << endl;

cout << "Post order traversal" << endl;

tree->postOrder(tree->getRoot());

cout << endl;

delete tree;

return 0;

}