Delete Node in a Bst
Given the root of a BST and a key, delete the node with that key (if it exists) and return the root of the updated BST. The result must still be a valid BST.
Constraints:
- The number of nodes is in the range
[0, 10^4]. -10^5 <= Node.val <= 10^5and all values are unique.
Intuition
1 82 / \3 4 124 / \ / \5 2 6 10 14First find the node, using the usual BST search. The hard part is removing it. There are three cases, depending on how many children it has:
- No children (a leaf): just remove it.
- One child: the child takes its place.
- Two children: we need to keep both subtrees. Every value in the right subtree is larger than every value in the left subtree, so we can hang the entire right subtree under the rightmost node of the left subtree, and then let the left child replace the deleted node.
For example, deleting 4: its left child is 2 and its right child is 6. The rightmost node of 4's left subtree is 2, so 6 becomes the right child of 2, and 2 replaces 4 under 8.
Approach: Find the Parent, Then Rewire
- If the root itself holds the key, return
helper(root). - Otherwise walk down with a pointer
cur. At each step look at the child that would hold the key: ifkey < cur.valcheckcur.left, elsecur.right. When that child's value equals the key, replace the child withhelper(child)and stop. - Return the original root.
helper(node) returns the subtree that should take the node's place:
- No left child: return
node.right. - No right child: return
node.left. - Both exist: find the rightmost node of the left subtree with
findLastRight, set itsrighttonode.right, and returnnode.left.
The rewiring keeps order intact because the right subtree is entirely larger than anything in the left subtree.
Code
class Solution {TreeNode* findLastRight(TreeNode* node) {while (node->right != nullptr) node = node->right;return node;}TreeNode* helper(TreeNode* node) {if (node->left == nullptr) return node->right;if (node->right == nullptr) return node->left;TreeNode* rightChild = node->right;TreeNode* lastRight = findLastRight(node->left);lastRight->right = rightChild;return node->left;}public:TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr) return nullptr;if (root->val == key) return helper(root);TreeNode* cur = root;while (cur != nullptr) {if (key < cur->val) {if (cur->left != nullptr && cur->left->val == key) {cur->left = helper(cur->left);break;}cur = cur->left;} else {if (cur->right != nullptr && cur->right->val == key) {cur->right = helper(cur->right);break;}cur = cur->right;}}return root;}};
Complexity
Finding the node takes O(h), and findLastRight walks down one more path of at most O(h).
The solution is iterative and rewires pointers in place.