In C++, use this code Node.h, BSTree.h, BSTree.cpp to implement a binary search tree. Specifically, you will implement a printPreorder, printInorder, printPostorder, and findNode member functions. Do not make other changes to the Node.h or the BSTree.h. Ensure that you document any changes that you make in BSTree.cpp with comments. I left the member function headers in the code, so you just need to fill in the code.

Demonstrate that you did this correctly by building a main program that uses these functions to build an output that looks very similar to HW Output.

Thanks!

*******Node.h*****

#ifndef NODE_

#define NODE_

#include

using namespace std;

// A generic tree node class

//Placeholder for a composite data type

class Datatype{

private:

int number;

};

//Binary Tree Node

class Node {

private:

int key;

Datatype data;

Node* left;

Node* right;

Node* parent;

public:

Node() { key=-1; left=nullptr; right=nullptr; parent = nullptr;};

void setKey(int aKey) { key = aKey; };

void setLeft(Node* aLeft) { left = aLeft; };

void setRight(Node* aRight) { right = aRight; };

void setParent(Node* aParent) { parent = aParent; };

int Key() { return key; };

Node* Left() { return left; };

Node* Right() { return right; };

Node* Parent() { return parent; };

};

#endif

******BSTree.h*****

#ifndef BSTREE_

#define BSTREE_

#include

using namespace std;

#include "Node.h"

// Binary Search Tree class

class BSTree {

private:

Node* root;

void addNode(int key, Node* leaf);

Node* deleteNode(Node* node, int key);

void freeNode(Node* leaf);

public:

BSTree();

~BSTree();

Node* Root() { return root; }

void setRoot(Node * _root) {root = _root;}

void addNode(int key);

Node* findNode(int key, Node* parent);

void printPreorder(Node* node);

void printInorder(Node* node);

void printPostorder(Node* node);

void deleteNode(int key);

Node* min(Node* node);

Node* max(Node* node);

Node* successor(int key, Node* parent);

Node* predecessor(int key, Node* parent);

};

#endif //BST

********BSTree.cpp****

#include "BSTree.h"

// Constructor

BSTree::BSTree() {

root = nullptr;

}

// Destructor

BSTree::~BSTree() {

if (root !=nullptr)

freeNode(root);

}

// Free the node

void BSTree::freeNode(Node* leaf)

{

if ( this->Root() == leaf)

{

}

else if ( leaf != nullptr )

{

freeNode(leaf->Left());

freeNode(leaf->Right());

delete leaf;

}

}

// Add a node

void BSTree::addNode(int key)

{

// No elements. Add the root

if ( root == nullptr ) {

Node* n = new Node();

n->setKey(key);

root = n;

}

else {

addNode(key, root);

}

}

// Add a node (private)

void BSTree::addNode(int key, Node* leaf) {

if ( key <= leaf->Key() )

{

if ( leaf->Left() != nullptr )

addNode(key, leaf->Left());

else {

Node* n = new Node();

n->setKey(key);

n->setParent(leaf);

leaf->setLeft(n);

}

}

else

{

if ( leaf->Right() != nullptr )

addNode(key, leaf->Right());

else {

Node* n = new Node();

n->setKey(key);

n->setParent(leaf);

leaf->setRight(n);

}

}

}

// Find a node

Node* BSTree::findNode(int key, Node* node)

{

}

// Print the BSTree

void BSTree::printPreorder(Node* node)

{

}

void BSTree::printInorder(Node* node)

{

}

void BSTree::printPostorder(Node* node)

{

if ( node != nullptr)

{

}

}

// Find the node with min key

// Traverse the left sub-BSTree recursively

// till left sub-BSTree is empty to get min

Node* BSTree::min(Node* node)

{

Node* tempNode = node;

if ( node == nullptr )

tempNode = nullptr;

else if ( node->Left() )

{

tempNode = min(node->Left());

}

else

tempNode = node;

return tempNode;

}

// Find the node with max key

// Traverse the right sub-BSTree recursively

// till right sub-BSTree is empty to get max

Node* BSTree::max(Node* node)

{

Node * tempNode = node;

if ( node == nullptr )

tempNode = nullptr;

else if ( node->Right() )

tempNode = max(node->Right());

else

tempNode = node;

return tempNode;

}

// Find successor to a node

// Find the node, get the node with max value

// for the right sub-BSTree to get the successor

Node* BSTree::successor(int key, Node *node)

{

Node *successor = nullptr;

Node *current = root;

if(root == nullptr)

return NULL;

while(current->Key() != key){

/* If node value is greater than the node which are looking for, then go to left sub tree

Also when we move left, update the successor pointer to keep track of lst left turn */

if(current->Key() >key){

successor = current;

current= current->Left();

}

/* Else take right turn and no need to update successor pointer */

else

current = current->Right();

}

/*Once we reached at the node for which inorder successor is to be found, check if it has right sub tree, if yes then find the minimum in that right sub tree and return that node Else last left turn taken node is already stored in successor pointer and will be returned*/

if(current && current->Right()){

successor = min(current->Right());

}

return successor;

}

// Find predecessor to a node

// Find the node, get the node with max value

// for the left sub-BSTree to get the predecessor

Node* BSTree::predecessor(int key, Node *node)

{

Node* current = findNode(key, node);

if (current == nullptr)

{ return nullptr; }

if (current->Left() !=nullptr)

{

return max(current->Left());

} else

{

Node *tempParent = current->Parent();

while (tempParent !=nullptr) {

if (current == tempParent->Right() ){

break;

}

current = tempParent;

tempParent = current->Parent();

}

return tempParent;

}

}

void BSTree::deleteNode(int key)

{

if (deleteNode(Root(), key) == nullptr)

setRoot(nullptr);

}

//deleteNode (Private)

Node* BSTree::deleteNode(Node* root,int key)

{

/* Given a binary search tree and a key, this function deletes the key

and returns the new root */

if(root == nullptr) return root;

else if(key < root->Key())

root->setLeft( deleteNode(root->Left(),key));

else if(key > root->Key())

root->setRight( deleteNode(root->Right(), key) );

else {

// Case 1: No Child

if(root->Left() == nullptr && root->Right() == nullptr){

delete root;

root = nullptr;

// Case 2: one child

} else if(root->Left() == nullptr){

Node *temp = root;

root = root->Right();

delete temp;

} else if(root->Right() == nullptr){

Node *temp = root;

root = root->Left();

delete temp;

} else{

Node *temp = min(root->Right());

root->setKey(temp->Key() );

root->setRight( deleteNode(root->Right(), temp->Key() ) );

}

}

return root;

}

*******Output*****

Adding 100

Adding 200

Adding 400

Preorder Print: 300 100 200 400

Inorder Print: 100 200 300 400

Postorder Print: 100 200 400 300

Node 500 not found

Node 600 not found

Min=100

Max=400

Successor to 300=400

Predecessor to 300=200

Deleting 300

Preorder Print: 200 100 400

Deleting entire tree pointer