Question

The Binary Search Tree implementation for bst.zip. 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 (the program should not crash upon exiting).

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 < x->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 < y->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 < p->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 << p->getItem() << endl;
   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 << "Traversing tree in-order" << endl;
bst.traverse();
cout << endl;

return 0;
}

Answer 1

// the destructor function wll use the deleteNode fucntion already implemented in above class. Here we are not concerned about order although it will be postorder in this case as we have to destruct the whole tree.;

void destructTree(Node* root) {

    if (root == nullptr) return;

// first delete both subtress recursively and order does not matter . We can delete like a //ordinary binary tree.

    deleteNode(root->left);

    deleteNode(root->right);

// then delete the node/root.

    cout << "deleting node: " << root->data;

     deleteNode(root);

}