LC 0450 [M] Delete Node in a BST - ALawliet/algorithms GitHub Wiki

# 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]:
        def inordersuccessor(root, parent):
            pre = parent
            cur = root
            # go as far left as possible to find the smallest value than the parent, which is the inorder successor of the parent
            while cur.left:
                pre = cur
                cur = cur.left
            # then we can just delete the parent of that smallest value
            self.deleteNode(pre, cur.val)
            return cur
    
        if not root: return None
        
        if root.val == key:
            # if leaf: do nothing
            if not root.left and not root.right: return None
            
            # if 1 child: use the subtree that exists
            if not root.left: return root.right
            if not root.right: return root.left
            
            # 2 children: find inorder successor and replace e.g. 3<-(5)->6->7 to 3<-6->7
            node = inordersuccessor(root.right, root)
            root.val = node.val
            
        # traverse only the side we need using BST property
        elif key < root.val:
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:
            root.right = self.deleteNode(root.right, key)
            
        return root