/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode *deleteNode(TreeNode *root, int key) {
TreeNode *delNode = root, *parent = nullptr;
while (delNode != nullptr) {
if (delNode->val < key) {
parent = delNode;
delNode = delNode->right;
} else if (key < delNode->val) {
parent = delNode;
delNode = delNode->left;
} else {
break; // find key
}
}
if (delNode == nullptr) {
return root; // key doesn't exist in BST.
}
if (parent == nullptr) {
// root->val == key is true. Delete root.
return deleteTreeNode(root);
} else if (parent->left != nullptr && parent->left == delNode) {
parent->left = deleteTreeNode(delNode);
} else {
parent->right = deleteTreeNode(delNode);
}
return root;
}
private:
TreeNode *deleteTreeNode(TreeNode *delNode) {
if (delNode->left == nullptr) {
TreeNode *x = delNode->right;
delete delNode;
return x;
}
TreeNode *predecessor = delNode->left;
while (predecessor->right != nullptr) {
predecessor = predecessor->right;
}
TreeNode *y = delNode->left;
predecessor->right = delNode->right;
delete delNode;
return y;
}
};
H is the height of the BST.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode *deleteNode(TreeNode *root, int key) {
if (root == nullptr) {
return nullptr;
}
if (root->val < key) {
root->right = deleteNode(root->right, key);
return root;
}
if (key < root->val) {
root->left = deleteNode(root->left, key);
return root;
}
// root->val == key is true. root should be deleted.
if (root->left != nullptr) {
int predVal = findPredVal(root);
root->val = predVal;
root->left = deleteNode(root->left, predVal);
return root;
}
if (root->right != nullptr) {
int succVal = findSuccVal(root);
root->val = succVal;
root->right = deleteNode(root->right, succVal);
return root;
}
// root is a leaf
delete root;
return nullptr;
}
private:
int findPredVal(TreeNode *root) {
TreeNode *predecessor = root->left;
while (predecessor->right != nullptr) {
predecessor = predecessor->right;
}
return predecessor->val;
}
int findSuccVal(TreeNode *root) {
TreeNode *successor = root->right;
while (successor->left != nullptr) {
successor = successor->left;
}
return successor->val;
}
};
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode *deleteNode(TreeNode *root, int key) {
if (root == nullptr) {
return nullptr;
}
if (root->val < key) {
root->right = deleteNode(root->right, key);
} else if (key < root->val) {
root->left = deleteNode(root->left, key);
} else {
// root->val == key is true.
if (root->left == nullptr && root->right == nullptr) {
delete root;
return nullptr;
}
if (root->left == nullptr) {
TreeNode *x = root->right;
delete root;
return x;
}
if (root->right == nullptr) {
TreeNode *y = root->left;
delete root;
return y;
}
int predVal = findPredecessorVal(root);
root->val = predVal;
root->left = deleteNode(root->left, predVal);
}
return root;
}
private:
int findPredecessorVal(TreeNode *node) {
TreeNode *predecessor = node->left;
while (predecessor->right != nullptr) {
predecessor = predecessor->right;
}
return predecessor->val;
}
};
H is the height of the BST
H is the height of the BST
My Solution Solution 1: DFS (recursion) The Key Idea for Solving This Coding Question C++ Code /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right;
Jun 6, 2025MyCircularQueueO(k)
Apr 20, 2025O(m)
Mar 4, 2025O(n)n is the length of nums.
Feb 19, 2025or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up