Please solve both parts in C++, and show screenshots of the completed running code. Cheers!

(a) The code in the destructor of the BST class is empty. Complete the destructor so the memory allocated for each node in the BST is freed. Make a couple of different trees in your main method or in a function to test the destructor (if you create the tree as a local variable in a function, it should be destroyed when the function exits, and the variable goes out of scope). Leave some print statements in your destructor that outputs each node that is being deallocated so you can see that it is working.

(b) Write a function that recursively determines if a BST is \"nearly complete.\" Our definition of \"nearly complete\" is one where, for every node n in the tree, the height of n's left subtree differs by at most 1 from the height of n's right subtree. For example, if the left subtree tree has a height of 4 and the right subtree has a height of 5 then the tree is nearly complete. But if the left subtree has a height of 4 and the right subtree has a height of 6 then the tree is not nearly complete. Note that this properly must apply to every node. Test your function on at least 2 trees that are not nearly complete and 3 trees that are nearly complete.

bst.zip (includes the following files below in c++):

bst.h:

#pragma once

#include

#include \"node.cpp\"

using namespace std;

template

class BST

{

public:

BST();

~BST();

void insert(T item);

Node* find(T item);

void deleteNode(Node *z);

void traverse();

private:

Node* treeSearch(Node *p, T item);

void inOrder(Node *p);

Node* successor(Node *p);

void transplant(Node *u, Node *v);

Node *root;

};

bst.cpp:

#include

#include \"bst.h\"

using namespace std;

template

BST::BST() : root(nullptr)

{

}

template

BST::~BST()

{

// This would be a good place to delete the nodes in the tree

}

// Inserts a new node at the front of the list

template

void BST::insert(T item)

{

// First search for the insertion point

Node *y = nullptr;

Node *x = root;

while (x != nullptr)

{

y = x; // Remember previous node

// Update x to a child pointer

if (item getItem())

x = x->getLeft();

else

x = x->getRight();

}

// At this point, y points to the node where we should

// insert the new node.

// Create a new node with the insertion value

Node *newNode = new Node(item);

newNode->setParent(y); // Set parent to Y

if (y==nullptr)

{

root = newNode; // First node

}

else

{

// Set new node as left or right child of y

if (item getItem())

y->setLeft(newNode);

else

y->setRight(newNode);

}

}

template

Node* BST::find(T item)

{

if (root == nullptr)

return nullptr;

return treeSearch(root, item);

}

template

Node* BST::treeSearch(Node *p, T item)

{

if (p == nullptr)

return nullptr;

if (p->getItem() == item)

return p;

if (item getItem())

return treeSearch(p->getLeft(), item);

else

return treeSearch(p->getRight(), item);

}

template

void BST::traverse()

{

inOrder(root);

}

template

void BST::inOrder(Node *p)

{

if (p != nullptr)

{

inOrder(p->getLeft());

cout getItem()

inOrder(p->getRight());

}

}

template

Node* BST::successor(Node *p)

{

if (p->getRight() != nullptr)

{

p = p->getRight();

while (p->getLeft() != nullptr)

{

p = p->getLeft();

}

return p;

}

else

{

Node* parent = p->getParent();

while ((parent != nullptr) && (p == parent->getRight()))

{

p = parent;

parent = parent->getParent();

}

return parent;

}

}

template

void BST::deleteNode(Node *z)

{

if (z->getLeft() == nullptr)

transplant(z, z->getRight());

else if (z->getRight() == nullptr)

transplant(z, z->getLeft());

else

{

Node *y;

// Find y as the minimum in z's right subtree

y = z->getRight();

while (y->getLeft() != nullptr)

{

y = y->getLeft();

}

// Y's right subtree to Z's right subtree

if (y->getParent() != z)

{

transplant(y, y->getRight());

y->setRight(z->getRight());

y->getRight()->setParent(y);

}

// Swap y and z and y's left subtree to z's left subtree

transplant(z, y);

y->setLeft(z->getLeft());

y->getLeft()->setParent(y);

}

}

template

void BST::transplant(Node *u, Node *v)

{

if (u->getParent() == nullptr)

root = v;

else if (u == u->getParent()->getLeft())

u->getParent()->setLeft(v);

else

u->getParent()->setRight(v);

if (v != nullptr)

v->setParent(u->getParent());

}

node.h:

#pragma once

#include

using namespace std;

template

class Node

{

public:

Node();

Node(T item);

~Node();

T& getItem();

void setLeft(Node *next);

void setRight(Node *next);

void setParent(Node *next);

Node* getLeft();

Node* getRight();

Node* getParent();

private:

T item;

Node* left;

Node* right;

Node* parent;

};

node.cpp:

#include

#include \"node.h\"

template

Node::Node()

{

left = nullptr;

right = nullptr;

parent = nullptr;

}

template

Node::Node(T item) : item(item)

{

left = nullptr;

right = nullptr;

parent = nullptr;

}

template

Node::~Node()

{

}

template

Node* Node::getLeft()

{

return left;

}

template

Node* Node::getRight()

{

return right;

}

template

Node* Node::getParent()

{

return parent;

}

template

void Node::setLeft(Node *n)

{

left = n;

}

template

void Node::setRight(Node *n)

{

right = n;

}

template

void Node::setParent(Node *n)

{

parent = n;

}

template

T& Node::getItem()

{

return item;

}

main:

#include \"bst.cpp\"

#include

using namespace std;

int main()

{

BST bst;

bst.insert(5);

bst.insert(3);

bst.insert(2);

bst.insert(5);

bst.insert(7);

bst.insert(8);

Node *temp = bst.find(5);

bst.deleteNode(temp);

temp = bst.find(7);

bst.deleteNode(temp);

temp = bst.find(5);

bst.deleteNode(temp);

cout

bst.traverse();

cout

return 0;

}