How do you delete the node of a tree with edge cases applied to it ..
Tried to iterate to the element of the node in which if its the root its just to delete it recursively but if I wanted to delete in somewhere in the middle getting stuck ..
3
In C++, deleting a node in a Binary Search Tree (BST) involves three main cases:
- Node has no children (leaf node): Simply remove the node.
- Node has one child: Replace the node with its child and delete the node.
- Node has two children: Find the node’s in-order successor (smallest node in the right subtree) or in-order predecessor (largest in the left subtree), replace the node’s value with that of the successor or predecessor, and delete the successor or predecessor node.
Here’s a basic implementation for deleting a node in a BST in C++:
struct Node {
int key;
Node* left, * right;
};
// Helper function to find the minimum node in the subtree
Node* minValueNode(Node* node) {
Node* current = node;
while (current && current->left != nullptr)
current = current->left;
return current;
}
// Recursive function to delete a node
Node* deleteNode(Node* root, int key) {
if (root == nullptr) return root;
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else {
if (root->left == nullptr) {
Node* temp = root->right;
delete root;
return temp;
}
else if (root->right == nullptr) {
Node* temp = root->left;
delete root;
return temp;
}
Node* temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
return root;
}
In this code:
• minValueNode helps to find the in-order successor.
• deleteNode recursively finds the node to be deleted and handles all edge cases (no children, one child, two children).
Make sure to adjust for the specific tree structure and edge cases in your implementation.
1