450. Delete Node in a BST
Tree, BST, BT, Review ·Problem Statement
link: https://leetcode.com/problems/delete-node-in-a-bst/ https://leetcode.cn/problems/delete-node-in-a-bst/
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.
Basically, the deletion can be divided into two stages:
Search for a node to remove. If the node is found, delete the node.
Example:
Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Input: root = [], key = 0
Output: []
Solution Approach
Algorithm
Implement
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if root is None:
return None
if root.val > key:
root.left = self.deleteNode(root.left, key)
elif root.val < key:
root.right = self.deleteNode(root.right, key)
elif root.left is None or root.right is None:
root = root.left if root.left else root.right
else:
successor_parent = root
successor = root.right
while successor.left:
successor_parent = successor
successor = successor.left
root.val = successor.val
if successor_parent.left == successor:
successor_parent.left = self.deleteNode(successor_parent.left, successor.val)
else:
successor_parent.right = self.deleteNode(successor_parent.right, successor.val)
return root