Problem
Given the root of a Binary Search Tree and an integer key, delete the node whose value is equal tokey and return the root of the modified tree.
After deletion, the tree must continue to satisfy the Binary Search Tree property: values smaller than a node are stored in its left subtree, while values greater than the node are stored in its right subtree.
If the node does not exist, return the tree unchanged.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
root:
5
/ \
3 6
/ \ \
2 4 7
key = 3Output
5
/ \
4 6
/ \
2 7Example 2
Input
root:
5
/ \
3 6
/ \ \
2 4 7
key = 3Output
5
/ \
2 6
\ \
4 7Solution
This solution uses Binary Search Tree properties to locate the node that needs to be deleted. If the key is smaller than the current node, we recursively search the left subtree. If it is larger, we search the right subtree.When the node is found, there are three cases. If it has no left child, we return its right child. If it has no right child, we return its left child. If it has both children, we find the smallest node in the right subtree, copy its value into the current node, and then delete that successor node.
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null)
return null;
if (key < root.val) {
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
root.right = deleteNode(root.right, key);
} else {
if (root.left == null)
return root.right;
if (root.right == null)
return root.left;
TreeNode successor = root.right;
while (successor.left != null) {
successor = successor.left;
}
root.val = successor.val;
root.right = deleteNode(root.right, successor.val);
}
return root;
}
}Complexity
The search and deletion follow a single path from the root to the target node. Finding the successor may also traverse the height of the tree, so the time complexity isO(h), where h is the height of the tree. For a balanced BST, this is O(log n), while for a skewed tree it can be O(n).
The recursive calls use space proportional to the height of the tree, so the extra space complexity is
O(h).