https://leetcode.com/problems/delete-node-in-a-bst/
Intuition
- Node is a leaf, and one could delete it straightforward

- Node is not a leaf and has a right child. Then the node could be replaced by its successor which is somewhere lower in the right subtree. Then one could proceed down recursively to delete the successor.

- Node is not a leaf, has no right child and has a left child. That means that its successor is somewhere upper in the tree but we don’t want to go back. Let’s use the predecessor here which is somewhere lower in the left subtree. The node could be replaced by its predecessor and then one could proceed down recursively to delete the predecessor.

Algorithm
- If
key > root.val
then delete the node to delete is in the right subtreeroot.right = deleteNode(root.right, key)
. - If
key < root
.val then delete the node to delete is in the left subtreeroot.left = deleteNode(root.left, key)
. - If
key == root.val
then the node to delete is right here. Let’s do it :- If the node is a leaf, the delete process is straightforward :
root = null
. - If the node is not a leaf and has the right child, then replace the node value by a successor value
root.val = successor.val
, and then recursively delete the successor in the right subtreeroot.right = deleteNode(root.right, root.val)
. - If the node is not a leaf and has only the left child, then replace the node value by a predecessor value
root.val = predecessor.val
, and then recursively delete the predecessor in the left subtreeroot.left = deleteNode(root.left, root.val)
.
- If the node is a leaf, the delete process is straightforward :
- Return
root
.
Java Solution
class Solution {
public int predecessor(TreeNode root) {
root = root.left;
while (root.right != null) {
root = root.right;
}
return root.val;
}
public int successor(TreeNode root) {
root = root.right;
while (root.left != null) {
root = root.left;
}
return root.val;
}
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (key > root.val) {
root.right = deleteNode(root.right, key);
} else if (key < root.val) {
root.left = deleteNode(root.left, key);
} else {
if (root.left == null && root.right == null) {
root = null;
} else if (root.right != null) {
root.val = successor(root);
root.right = deleteNode(root.right, root.val);
} else {
root.val = predecessor(root);
root.left = deleteNode(root.left, root.val);
}
}
return root;
}
}