Deleting a node from a BST is one of the most important operations because it affects the tree’s structure and the ordering property. Proper handling ensures that the BST property — all left descendants are smaller and all right descendants are larger — is maintained. This operation requires careful management of pointers and consideration of several cases.
Understanding the Problem
There are three primary scenarios when deleting a node in a BST:
- The node is a leaf (has no children).
- The node has only one child.
- The node has two children.
For nodes with two children, the common approach is to replace the node with its inorder successor (smallest node in the right subtree) or inorder predecessor (largest node in the left subtree). This ensures the BST property remains intact after deletion.
Program: Delete a Node from BST (Inorder Successor)
This program demonstrates how to delete a node using inorder successor while maintaining the BST property. It also includes insertion and inorder traversal to test the deletion.
#include <stdio.h>
#include <stdlib.h>
// Structure for a BST node
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
// Function to create a new node
Node* createNode(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}
// Insert a node into the BST
Node* insert(Node* root, int value) {
if (root == NULL)
return createNode(value);
if (value < root->data)
root->left = insert(root->left, value);
else if (value > root->data)
root->right = insert(root->right, value);
return root;
}
// Inorder traversal to display BST
void inorder(Node *root) {
if (root == NULL) return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
// Find the node with minimum value in a subtree
Node* findMin(Node* root) {
while (root->left != NULL)
root = root->left;
return root;
}
// Delete a node from BST
Node* deleteNode(Node* root, int key) {
if (root == NULL) return root;
if (key < root->data)
root->left = deleteNode(root->left, key);
else if (key > root->data)
root->right = deleteNode(root->right, key);
else {
// Node with only one child or no child
if (root->left == NULL) {
Node* temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL) {
Node* temp = root->left;
free(root);
return temp;
}
// Node with two children: replace with inorder successor
Node* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
int main() {
Node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
insert(root, 60);
insert(root, 80);
printf("Inorder before deletion: ");
inorder(root);
printf("\n");
int key = 50;
root = deleteNode(root, key);
printf("Inorder after deleting %d: ", key);
inorder(root);
printf("\n");
return 0;
}In this program, deletion handles all three cases: leaf node, node with one child, and node with two children. Using the inorder successor ensures that the BST property is maintained after deletion. Inorder traversal before and after deletion confirms the correct structure.
Program: Delete a Node from BST (Inorder Predecessor)
This program demonstrates how to delete a node while maintaining the BST property. Instead of using the inorder successor, it replaces the node with its inorder predecessor when both children exist.
#include <stdio.h>
#include <stdlib.h>
// Structure for a BST node
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
// Function to create a new node
Node* createNode(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}
// Insert a node into the BST
Node* insert(Node* root, int value) {
if (root == NULL)
return createNode(value);
if (value < root->data)
root->left = insert(root->left, value);
else if (value > root->data)
root->right = insert(root->right, value);
return root;
}
// Inorder traversal to display BST
void inorder(Node *root) {
if (root == NULL) return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
// Find the node with maximum value in a subtree
Node* findMax(Node* root) {
while (root->right != NULL)
root = root->right;
return root;
}
// Delete a node from BST using inorder predecessor
Node* deleteNode(Node* root, int key) {
if (root == NULL) return root;
if (key < root->data)
root->left = deleteNode(root->left, key);
else if (key > root->data)
root->right = deleteNode(root->right, key);
else {
// Node with only one child or no child
if (root->left == NULL) {
Node* temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL) {
Node* temp = root->left;
free(root);
return temp;
}
// Node with two children: replace with inorder predecessor
Node* temp = findMax(root->left);
root->data = temp->data;
root->left = deleteNode(root->left, temp->data);
}
return root;
}
int main() {
Node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
insert(root, 60);
insert(root, 80);
printf("Inorder before deletion: ");
inorder(root);
printf("\n");
int key = 50;
root = deleteNode(root, key);
printf("Inorder after deleting %d: ", key);
inorder(root);
printf("\n");
return 0;
}When a node has no children, it is simply removed. If it has one child, it is replaced by that child. For nodes with two children, this version replaces the value with its inorder predecessor (the largest node in the left subtree) before deleting that predecessor. This approach works just as well as using the inorder successor and keeps the BST property intact.
FAQs
Q1: What happens if we delete a node with two children?
We replace it with its inorder successor or predecessor and then delete that successor/predecessor.
Q2: What is the time complexity of deletion?
Average case: O(log n) for balanced BST; worst case: O(n) for unbalanced BST.
Q3: Can we delete a node iteratively?
Yes, deletion can also be implemented iteratively, but recursion simplifies handling child cases.
Q4: Does deletion change the number of nodes in the BST?
Yes, each deletion reduces the total node count by one.
Conclusion
Deleting a node from a BST requires careful handling to maintain the tree’s ordering property. By considering all possible node cases and using the inorder successor for nodes with two children, we ensure the BST remains valid. Mastering deletion strengthens understanding of BST operations and tree-based algorithms.
References & Additional Resources
The following books and online resources provide theoretical foundations and practical examples for understanding Binary Search Tree (BST) operations, including deletion, traversal, and manipulation in C.
- Thareja, R. (2011). Data Structures Using C. Oxford University Press – Comprehensive coverage of BSTs, their properties, and operations like insertion, deletion, and traversal.
- GeeksforGeeks: BST Deletion – Step-by-step explanation and code examples for deleting nodes in a BST.
- Programiz: Binary Search Tree Operations – Beginner-friendly guide on implementing insertion, deletion, and search operations.
- Tutorialspoint: Tree Traversals and Manipulations – Overview of tree algorithms and operations.
