Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Node* BinarySearchTree::deleteKey(Node *root, int key) {
- if (!root) return root;
- if (key < root->val) {
- // If the key to be deleted is smaller than the root's key, then it lies in left subtree
- root->left = deleteKey(root->left, key);
- } else if (key > root->val) {
- // If the key to be deleted is greater than the root's key, then it lies in right subtree
- root->right = deleteKey(root->right, key);
- } else {
- // Node with only one child or no child
- if (!root->left) {
- Node *temp = root->right;
- free(root);
- return temp;
- } else if (!root->right) {
- Node *temp = root->left;
- free(root);
- return temp;
- }
- // Node with two children: get the inorder successor
- Node *temp = minNode(root->right);
- // Copy the inorder successor's content to this node
- root->val = temp->val;
- // Delete the inorder successor
- root->right = deleteKey(root->right, temp->val);
- }
- return root;
- }
Add Comment
Please, Sign In to add comment