I need help with the remove function. #ifndef NodeBST_h #define NodeBST_h templa
ID: 3867477 • Letter: I
Question
I need help with the remove function.
#ifndef NodeBST_h
#define NodeBST_h
template <class ItemType>
class Node
{
private:
ItemType item;
Node *right;
Node *left;
public:
Node();
Node(const ItemType& aNum);
void setItem(const ItemType& aNum);
ItemType getItem() const;
void setRight(Node* rightPtr);
void setLeft(Node* leftPtr);
Node* getRight() const;
Node* getLeft() const;
};
#endif
#include <stdio.h>
#include "NodeBST.h"
#include <iostream>
template <class ItemType>
Node<ItemType>::Node()
{
right = nullptr;
left = nullptr;
} //end default constructor
template <class ItemType>
Node<ItemType>::Node(const ItemType& aNum): item(aNum), right(nullptr), left(nullptr)
{
} //end 2nd constructor
template <class ItemType>
void Node<ItemType>::setItem(const ItemType& aNum)
{
item = aNum;
}
template <class ItemType>
void Node<ItemType>::setRight(Node* rightNodePtr)
{
right = rightNodePtr;
}
template <class ItemType>
void Node<ItemType>::setLeft(Node* leftNodePtr)
{
left = leftNodePtr;
}
template <class ItemType>
ItemType Node<ItemType>::getItem() const
{
return item;
}
template <class ItemType>
Node<ItemType>* Node<ItemType>::getRight() const
{
return right;
}
template <class ItemType>
Node<ItemType>* Node<ItemType>::getLeft() const
{
return left;
}
#ifndef BST_h
#define BST_h
#include <stdio.h>
#include "NodeBST.cpp"
template <class ItemType>
class BST
{
private:
Node<ItemType>* rootPtr;
protected:
int getHeightHelper(Node <ItemType>*subTreePtr) const;
Node<ItemType>* placeNode(Node<ItemType>* subTreePtr, Node<ItemType>* newNodePtr);
Node<ItemType>* FindMin(Node<ItemType>* rootPtr);
public:
BST();
BST(const ItemType& rootItem);
BST(const ItemType& rootItem,
const Node<ItemType>* leftTreePtr,
const Node<ItemType>* rightTreePtr);
void inOrder(Node<ItemType>* p);
bool isEmpty() const;
int getHeight() const;
bool add(const ItemType& newData);
void remove(const ItemType& data);
void displayInOrder();
};
#endif
#include "BST.h"
#include "BST.h"
#include "NodeBST.h"
#include <iostream>
using namespace std;
template <class ItemType>
BST<ItemType>::BST()
{
rootPtr = nullptr;
}
template <class ItemType>
BST<ItemType>::BST(const ItemType& rootItem)
{
rootPtr = rootItem;
rootPtr->setRight(nullptr);
rootPtr->setLeft(nullptr);
}
template <class ItemType>
bool BST<ItemType>:: isEmpty() const
{
return rootPtr ==nullptr;
}
template <class ItemType>
int BST<ItemType>::getHeightHelper(Node<ItemType>*subTreePtr) const
{
if(subTreePtr == nullptr)
return 0;
else
return 1 + max(getHeightHelper(subTreePtr->getLeft()),
getHeightHelper(subTreePtr->getRight()));
}
template <class ItemType>
int BST<ItemType>::getHeight() const
{
return getHeightHelper(rootPtr);
}
template <class ItemType>
bool BST<ItemType>::add(const ItemType& newData)
{
Node<ItemType> newNodePtr = Node<ItemType>(newData);
rootPtr = placeNode(rootPtr, &newNodePtr );
return true;
}
template <class ItemType>
Node<ItemType>* BST<ItemType>::placeNode(Node<ItemType>* subTreePtr, Node<ItemType>* newNodePtr)
{
Node<ItemType>*tempPtr;
tempPtr = rootPtr;
if(isEmpty())
return subTreePtr;
else if(subTreePtr->getItem() > newNodePtr->getItem())
{
tempPtr = placeNode(subTreePtr->getLeft(), newNodePtr);
subTreePtr->setLeft(tempPtr);
}
else
{
tempPtr = placeNode(subTreePtr->getRight(), newNodePtr);
subTreePtr->setRight(tempPtr);
}
return subTreePtr;
}
template <class ItemType>
void BST<ItemType>:: remove(const ItemType& data)
{
//Locate the element
bool found = false;
if (isEmpty())
{
wcout<< "This Tree is empty";
return;
}
Node<ItemType>* curr = rootPtr;
Node<ItemType>* parent;
while(curr != NULL)
{
if(curr->getItem() == data)
{
found = true;
break;
}
else
{
parent = curr;
if(data > curr->getItem())
curr = curr->getRight();
else
curr = curr->getLeft();
}
if(!found)
wcout << "Data not found"<<endl;
return;
}
// 3 cases :
// 1. We're removing a leaf node
// 2. We're removing a node with a single child
// 3. we're removing a node with 2 children
// Node with single child
if((curr->getLeft() == nullptr && curr->getRight() != nullptr) || (curr->getLeft() != nullptr && curr->getRight() == nullptr))
{
if(curr->getLeft() == NULL)
{
Node<ItemType> *temp = rootPtr;
rootPtr = rootPtr->getRight();
delete temp;
}
else
{
Node<ItemType> *temp = rootPtr;
rootPtr = rootPtr->getLeft();
delete temp;
}
}
else //left child present, no right child
{
if(parent->getLeft() == curr)
{
parent->setLeft() = curr->getLeft();
delete curr;
}
else
{
parent->getRight() = curr->getLeft();
delete curr;
}
}
return;
//Looking at a leaf node
if( curr->getLeft() == NULL && curr->getRight() == NULL)
{
//if(parent->getLeft() == curr->(parent->setLeft() = NULL;
//else parent->setRight() = NULL;
delete curr;
curr = nullptr;
//return;
}
//Node with 2 children
// replace node with smallest value in right subtree
else{
Node<ItemType> *temp = FindMin(rootPtr->getRight());
rootPtr->getItem() = temp->getItem();
rootPtr->getRight() = remove(temp->getItem());
}
//return rootPtr;
}
template <class ItemType>
Node<ItemType>* BST<ItemType>::FindMin(Node<ItemType>* rootPtr)
{
while(rootPtr->getLeft() != NULL)
rootPtr = rootPtr->getLeft();
return rootPtr;
}
template <class ItemType>
void BST<ItemType>:: displayInOrder()
{
inOrder(rootPtr);
}
template <class ItemType>
void BST<ItemType>::inOrder(Node<ItemType>* p)
{
if(p!=nullptr)
{
if(p->getLeft())
{
inOrder(p->getLeft());
wcout<< ", " ;
}
wcout<<p->getItem();
if(p->getRight())
{
wcout<< ", " ;
inOrder(p->getRight());
}
}
}
#include <iostream>
#include "BST.cpp"
int main()
{
BST<int> tree;
for (int i = 1; i<=21; i++)
{
int random = rand() %100;
cout<<random<<" -->";
tree.add(random);
}
tree.displayInOrder();
tree.remove(3);
tree.displayInOrder();
return 0;
}
Explanation / Answer
Fixed the code for remove as well as add. Given below are the modified files. When removing the min node , we also need the parent of the min node, so changed the parameters of the FindMin() function. I have added comments in remove to track the cases. Shown below is the output. Please don't forget to rate the answer if it helped. Thank you
BST.h
#ifndef BST_h
#define BST_h
#include <stdio.h>
#include "NodeBST.cpp"
template <class ItemType>
class BST
{
private:
Node<ItemType>* rootPtr;
protected:
int getHeightHelper(Node <ItemType>*subTreePtr) const;
Node<ItemType>* placeNode(Node<ItemType>* subTreePtr, Node<ItemType>* newNodePtr);
Node<ItemType>* FindMin(Node<ItemType>* rootPtr, Node<ItemType>* &minParent);
void remove(Node<ItemType>* node, Node<ItemType>* parent);
public:
BST();
BST(const ItemType& rootItem);
BST(const ItemType& rootItem,
const Node<ItemType>* leftTreePtr,
const Node<ItemType>* rightTreePtr);
void inOrder(Node<ItemType>* p);
bool isEmpty() const;
int getHeight() const;
bool add(const ItemType& newData);
void remove(const ItemType& data);
void displayInOrder();
};
#endif
BST.cpp
#include "BST.h"
#include "NodeBST.h"
#include <iostream>
using namespace std;
template <class ItemType>
BST<ItemType>::BST()
{
rootPtr = nullptr;
}
template <class ItemType>
BST<ItemType>::BST(const ItemType& rootItem)
{
rootPtr = rootItem;
rootPtr->setRight(nullptr);
rootPtr->setLeft(nullptr);
}
template <class ItemType>
bool BST<ItemType>:: isEmpty() const
{
return rootPtr ==nullptr;
}
template <class ItemType>
int BST<ItemType>::getHeightHelper(Node<ItemType>*subTreePtr) const
{
if(subTreePtr == nullptr)
return 0;
else
return 1 + max(getHeightHelper(subTreePtr->getLeft()),
getHeightHelper(subTreePtr->getRight()));
}
template <class ItemType>
int BST<ItemType>::getHeight() const
{
return getHeightHelper(rootPtr);
}
template <class ItemType>
bool BST<ItemType>::add(const ItemType& newData)
{
Node<ItemType>* newNodePtr = new Node<ItemType>(newData);
rootPtr = placeNode(rootPtr, newNodePtr );
return true;
}
template <class ItemType>
Node<ItemType>* BST<ItemType>::placeNode(Node<ItemType>* subTreePtr, Node<ItemType>* newNodePtr)
{
Node<ItemType>*tempPtr;
tempPtr = rootPtr;
if(subTreePtr == nullptr)
return newNodePtr;
else if(subTreePtr->getItem() > newNodePtr->getItem())
{
tempPtr = placeNode(subTreePtr->getLeft(), newNodePtr);
subTreePtr->setLeft(tempPtr);
}
else
{
tempPtr = placeNode(subTreePtr->getRight(), newNodePtr);
subTreePtr->setRight(tempPtr);
}
return subTreePtr;
}
template <class ItemType>
void BST<ItemType>:: remove(Node<ItemType>* curr, Node<ItemType>* parent)
{
if(curr == nullptr)
return;
// 3 cases :
// 1. We're removing a leaf node
// 2. We're removing a node with a single child
// 3. we're removing a node with 2 children
//Looking at a leaf node
if( curr->getLeft() == NULL && curr->getRight() == NULL)
{
if(parent == nullptr) //deleting the root
rootPtr = nullptr;
else
{
if(parent->getLeft() == curr)
parent->setLeft(NULL);
else
parent->setRight(NULL);
}
delete curr;
curr = nullptr;
return;
}
// Node with single child
if((curr->getLeft() == nullptr && curr->getRight() != nullptr) || (curr->getLeft() != nullptr && curr->getRight() == nullptr))
{
if(curr->getLeft() == NULL) //node to be deleted has right child
{
if(parent == nullptr) //deleting the root
rootPtr = curr->getRight(); //set root to the right child of node being deleted
else
{
if(parent->getLeft() == curr) //if node being deleted is left child of its parent
parent->setLeft(curr->getRight());
else //node being deleted is right child of its parent
parent->setRight(curr->getRight());
}
delete curr;
curr = nullptr;
return;
}
else // node to be delted has left child
{
if(parent == nullptr) //deleting the root
rootPtr = curr->getLeft(); //set root to the left child of node being deleted
else
{
if(parent->getLeft() == curr) //if node being deleted is left child of its parent
parent->setLeft(curr->getLeft());
else //node being deleted is right child of its parent
parent->setRight(curr->getLeft());
}
delete curr;
curr = nullptr;
return;
}
}
//Node with 2 children
// replace node with smallest value in right subtree
Node<ItemType> *minParent = curr;
Node<ItemType> *min = FindMin(rootPtr->getRight(), minParent);
curr->setItem(min->getItem()); //replace the value in the curr node with that of min
//recursively delete min node
remove(min, minParent);
}
template <class ItemType>
void BST<ItemType>:: remove(const ItemType& data)
{
//Locate the element
bool found = false;
if (isEmpty())
{
wcout<< "This Tree is empty";
return;
}
Node<ItemType>* curr = rootPtr;
Node<ItemType>* parent;
while(curr != NULL)
{
if(curr->getItem() == data)
{
found = true;
break;
}
else
{
parent = curr;
if(data > curr->getItem())
curr = curr->getRight();
else
curr = curr->getLeft();
}
}
if(!found)
wcout << "Data not found"<<endl;
else
remove(curr, parent);
}
//returns the min node and also sets its parent in the reference variable minParent
template <class ItemType>
Node<ItemType>* BST<ItemType>::FindMin(Node<ItemType>* rootPtr, Node<ItemType>* &minParent)
{
while(rootPtr->getLeft() != NULL)
{
minParent = rootPtr;
rootPtr = rootPtr->getLeft();
}
return rootPtr;
}
template <class ItemType>
void BST<ItemType>:: displayInOrder()
{
cout << " inorder traversal : ";
inOrder(rootPtr);
cout << endl;
}
template <class ItemType>
void BST<ItemType>::inOrder(Node<ItemType>* p)
{
if(p!=nullptr)
{
if(p->getLeft())
{
inOrder(p->getLeft());
wcout<< ", " ;
}
wcout<<p->getItem();
if(p->getRight())
{
wcout<< ", " ;
inOrder(p->getRight());
}
}
}
main
#include <iostream>
#include "BST.cpp"
int main()
{
BST<int> tree;
for (int i = 1; i<=21; i++)
{
int random = rand() %100;
cout<<random<<" -->";
tree.add(random);
}
tree.displayInOrder();
cout << "removing 3 and 29 ..." << endl;
tree.remove(3);
tree.remove(29);
tree.displayInOrder();
return 0;
}
output
7 -->49 -->73 -->58 -->30 -->72 -->44 -->78 -->23 -->9 -->40 -->65 -->92 -->42 -->87 -->3 -->27 -->29 -->40 -->12 -->3 -->
inorder traversal : 3, 3, 7, 9, 12, 23, 27, 29, 30, 40, 40, 42, 44, 49, 58, 65, 72, 73, 78, 87, 92
removing 3 and 29 ...
inorder traversal : 3, 7, 9, 12, 23, 27, 30, 40, 40, 42, 44, 49, 58, 65, 72, 73, 78, 87, 92