How to Delete a Node From Binary Search Tree in C++
This article will explain how to implement a function to delete a node in binary search tree data structure C++.
Delete Node in Binary Search Tree in C++
A binary search tree is a type of binary tree that stores a key value in each node. This key is used to construct an ordered tree so that each node’s key is greater than all the keys in its left subtree and less than keys in its right subtree.
Every node usually includes two pointers to the left and right nodes, but we also added another pointer to denote the parent node as it’s easier to implement remove member function.
Note that the following binary search tree implementation only includes the bare minimum of the member functions to demonstrate a node removal operation.
The BinSearchTree class is capable of storing only int types as key values. Most of the functions except remove utilize recursion, so we provide corresponding private member functions which are invoked internally. Generally, removing a node from the tree is a more complex operation than insertion and search, as it entails multiple scenarios.
The first and simplest scenario is when we need to remove a node with no children (consequently referred to as leaf node). Leaf nodes can be deallocated and nullptr assigned to its parent’s corresponding pointer.
The second case is removing the node with only one child. The latter can be solved by connecting the target’s parent to its child, and then we can deallocate the associated memory.
#include <iostream>
using std::cerr;
using std::cout;
using std::endl;
using std::string;
struct BSTreeNode {
int key{};
BSTreeNode *parent{};
BSTreeNode *left{};
BSTreeNode *right{};
} typedef BSTreeNode;
class BinSearchTree {
public:
BinSearchTree() {
root = nullptr;
size = 0;
};
BinSearchTree(std::initializer_list<int> list);
void insert(int k);
BSTreeNode *find(int k);
int remove(int k);
void print();
size_t getSize() const;
~BinSearchTree();
private:
BSTreeNode *root;
size_t size;
void freeNodes(BSTreeNode *&rnode);
void printTree(BSTreeNode *node);
void insertNode(BSTreeNode *&rnode, int k, BSTreeNode *pnode);
BSTreeNode **findNode(BSTreeNode *&rnode, int k);
};
BinSearchTree::BinSearchTree(std::initializer_list<int> list) {
root = nullptr;
size = 0;
for (const auto &item : list) {
insertNode(root, item, nullptr);
}
}
BinSearchTree::~BinSearchTree() { freeNodes(root); }
void BinSearchTree::freeNodes(BSTreeNode *&rnode) {
if (rnode != nullptr) {
freeNodes(rnode->left);
freeNodes(rnode->right);
delete rnode;
}
}
BSTreeNode *BinSearchTree::find(const int k) { return *findNode(root, k); }
BSTreeNode **BinSearchTree::findNode(BSTreeNode *&rnode, const int k) {
if (rnode == nullptr) return nullptr;
if (k == rnode->key) return &rnode;
if (k < rnode->key)
return findNode(rnode->left, k);
else
return findNode(rnode->right, k);
}
void BinSearchTree::print() {
if (size > 0)
printTree(root);
else
cout << "tree is empty!" << endl;
}
void BinSearchTree::printTree(BSTreeNode *rnode) {
if (rnode != nullptr) {
printTree(rnode->left);
cout << rnode->key << "; ";
printTree(rnode->right);
}
}
void BinSearchTree::insert(const int k) { insertNode(root, k, nullptr); }
void BinSearchTree::insertNode(BSTreeNode *&rnode, const int k,
BSTreeNode *pnode) {
if (rnode == nullptr) {
rnode = new BSTreeNode;
rnode->key = k;
rnode->parent = pnode;
rnode->left = nullptr;
rnode->right = nullptr;
size++;
} else {
if (k < rnode->key)
insertNode(rnode->left, k, rnode);
else if (k == rnode->key)
return;
else
insertNode(rnode->right, k, rnode);
}
}
size_t BinSearchTree::getSize() const { return size; }
int BinSearchTree::remove(const int k) {
auto ret = findNode(root, k);
if (ret == nullptr) return -1;
if (size == 1) {
auto tmp = root;
root = nullptr;
delete tmp;
size--;
return 0;
}
if ((*ret)->left == nullptr && (*ret)->right == nullptr) {
auto tmp = *ret;
if ((*ret)->key < (*ret)->parent->key)
(*ret)->parent->left = nullptr;
else
(*ret)->parent->right = nullptr;
delete tmp;
size--;
return 0;
}
if ((*ret)->left != nullptr && (*ret)->right != nullptr) {
auto leftmost = (*ret)->right;
while (leftmost && leftmost->left != nullptr) leftmost = leftmost->left;
(*ret)->key = leftmost->key;
if (leftmost->right != nullptr) {
leftmost->right->parent = leftmost->parent;
auto tmp = leftmost->right;
*leftmost = *leftmost->right;
leftmost->parent->left = leftmost;
delete tmp;
} else {
leftmost->parent->right = nullptr;
delete leftmost;
}
size--;
return 0;
} else {
if ((*ret)->left != nullptr) {
auto tmp = *ret;
*ret = (*ret)->left;
(*ret)->parent = tmp->parent;
delete tmp;
} else {
auto tmp = *ret;
*ret = (*ret)->right;
(*ret)->parent = tmp->parent;
delete tmp;
}
size--;
return 0;
}
}
int main() {
BinSearchTree bst = {6, 5, 11, 3, 2, 10, 12, 4, 9};
cout << "size of bst = " << bst.getSize() << endl;
bst.print();
cout << endl;
bst.insert(7);
bst.insert(8);
cout << "size of bst = " << bst.getSize() << endl;
bst.print();
cout << endl;
bst.remove(6);
bst.remove(2);
bst.remove(12);
cout << "size of bst = " << bst.getSize() << endl;
bst.print();
cout << endl;
return EXIT_SUCCESS;
}
size of bst = 9
2; 3; 4; 5; 6; 9; 10; 11; 12;
size of bst = 11
2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12;
size of bst = 8
3; 4; 5; 7; 8; 9; 10; 11;
The most complicated scenario is when the target node has two children. In this case, we need to correctly connect the nodes as well as retain element order as specified for the binary search tree structure. We need to replace the target node with the smallest key and part of the target’s right subtree.
The node with the smallest key is found in the leftmost place. Thus we should traverse the right subtree until we reach this node. Once the node is found, we can assign its key to the target node and then try to remove the former one as if it’s a node with a single child. The latter is implied by the fact that this node is the leftmost one in the given subtree. Thus, it can only have a right child or no child at all.
These three scenarios are implemented in separate if...else block in remove member function, but we also include additional code to check for some corner cases like when the element is not found in the tree, or the last node is removed. Note that the remove function can also be implemented in a recursive manner.
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook