Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST. The deletion can be divided into two stages:
Example 1:
Input: root = [5,3,6,2,4,null,7], key = 3 Output: [5,4,6,2,null,null,7] Explanation: Given key to delete is 3. So we find the node with value 3 and delete it. One valid answer is [5,4,6,2,null,null,7], shown in the above BST. Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.
Example 2:
Input: root = [5,3,6,2,4,null,7], key = 0 Output: [5,3,6,2,4,null,7] Explanation: The tree does not contain a node with value = 0.
Example 3:
Input: root = [], key = 0 Output: []
Constraints:
The number of nodes in the tree is in the range [0, 10^4]. -10^5 <= Node.val <= 10^5 Each node has a unique value. root is a valid binary search tree. -10^5 <= key <= 10^5
Follow up: Could you solve it with time complexity O(height of tree)?
One straightforward approach is to recursively traverse the BST, locate the node with the key to be deleted, and then handle the deletion based on the node's children.
Big O Analysis:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def deleteNode(root, key):
if not root:
return None
if key < root.val:
root.left = deleteNode(root.left, key)
elif key > root.val:
root.right = deleteNode(root.right, key)
else:
# Node found, perform deletion
if not root.left:
return root.right
elif not root.right:
return root.left
# Node has two children
# Find inorder successor (minimum in the right subtree)
successor = find_min(root.right)
root.val = successor.val
root.right = deleteNode(root.right, successor.val)
return root
def find_min(node):
while node.left:
node = node.left
return node
To achieve O(height) time complexity, where height is the height of the BST, we can use an iterative approach.
Big O Analysis:
root
is None, return None.root
.class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def deleteNode(root, key):
if not root:
return None
curr = root
parent = None
# Find the node to delete and its parent
while curr and curr.val != key:
parent = curr
if key < curr.val:
curr = curr.left
else:
curr = curr.right
# Key not found
if not curr:
return root
# Case 1: Node has no children
if not curr.left and not curr.right:
if not parent:
return None # Deleting the root node
if curr == parent.left:
parent.left = None
else:
parent.right = None
# Case 2: Node has one child
elif not curr.left or not curr.right:
child = curr.left if curr.left else curr.right
if not parent:
return child # Deleting the root node
if curr == parent.left:
parent.left = child
else:
parent.right = child
# Case 3: Node has two children
else:
# Find inorder successor (minimum in the right subtree)
successor = find_min(curr.right)
curr.val = successor.val
# Delete the successor (which has at most one child)
curr.right = deleteNode(curr.right, successor.val)
return root
def find_min(node):
while node.left:
node = node.left
return node