Table of Contents
Binary Search Tree Deletion Explanation:
When deleting a node in a Binary Search Tree (BST), there are three possible cases to consider:
Case 1:
Node has no children (leaf node):
In this case, we simply remove the node from the tree.
Case 2:
Node has one child:
We replace the node with its child.
Case 3:
Node has two children:
We find the inorder successor (or predecessor), copy its value to the node to be deleted, and then recursively delete the inorder successor.
Binary Search Tree Deletion C++ Code:
#include <iostream>
using namespace std;
class TreeNode {
public:
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) {
data = val;
left = nullptr;
right = nullptr;
}
};
class BST {
private:
TreeNode* root;
TreeNode* findMin(TreeNode* node) {
while (node->left != nullptr) {
node = node->left;
}
return node;
}
TreeNode* deleteRecursive(TreeNode* root, int val) {
if (root == nullptr) {
return root;
}
if (val < root->data) {
root->left = deleteRecursive(root->left, val);
} else if (val > root->data) {
root->right = deleteRecursive(root->right, val);
} else {
// Node with one or no child
if (root->left == nullptr) {
TreeNode* temp = root->right;
delete root;
return temp;
} else if (root->right == nullptr) {
TreeNode* temp = root->left;
delete root;
return temp;
}
// Node with two children
TreeNode* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteRecursive(root->right, temp->data);
}
return root;
}
TreeNode* insertRecursive(TreeNode* root, int val) {
if (root == nullptr) {
return new TreeNode(val);
}
if (val < root->data) {
root->left = insertRecursive(root->left, val);
} else {
root->right = insertRecursive(root->right, val);
}
return root;
}
public:
BST() {
root = nullptr;
}
void insert(int val) {
root = insertRecursive(root, val);
}
void remove(int val) {
root = deleteRecursive(root, val);
}
};
int main() {
BST bst;
bst.insert(15);
bst.insert(8);
bst.insert(20);
bst.insert(12);
bst.insert(25);
bst.remove(15);
return 0;
}
Code Explanation:
- findMin function finds the minimum node value in a given subtree by moving as far left as possible.
- deleteRecursive function is a recursive helper function that handles the different cases of deletion:
- If the value to delete is less than the current node’s data, go to the left subtree.
- If the value to delete is greater than the current node’s data, go to the right subtree.
- If the value to delete matches the current node’s data:
- If the node has no left child, replace it with the right child (or nullptr if no right child).
- If the node has no right child, replace it with the left child.
- If the node has both children, find the inorder successor (smallest value in the right subtree), copy its value to the current node, and then recursively delete the inorder successor node.
In the remove function, the deleteRecursive function is called to remove a specific value from the tree.
Time Complexity:
The time complexity for deleting a node in a balanced BST is O(log N) on average, where N is the number of nodes.
However, in the worst case (skewed tree), the time complexity can be O(N) similar to insertion.
Space Complexity:
The space complexity remains O(N) due to the storage of N nodes in the tree.
The efficiency of BST operations heavily relies on maintaining balance in the tree to avoid skewed structures, and in practice, self-balancing BSTs (like AVL trees or Red-Black trees) are often used to mitigate the worst-case time complexities.