450. Delete Node in a BST

[fockspaces]

BST:

1. each node val is unique
2. every subtree should also follow BST, that is, when root node is removed, we have to find the next successor (min_val of right subtree)

This technique is quite tricky, it only swap the value of root to the successor value, and then change the pass key to successor value, so that we can removed the original successor node as well

1. create a helper function called "next_bigger" for finding the sccuessor
2. we only need to search for the possible subtree (if key is larger than the current node, we can only traverse right subtree)
3. if the right child not exist, return left child
4. if the left child not exist, return the right child (it can be null)
5. if both the left and right childs exist, we should make a swap btw successor and current root 5-1. find next bigger node 5-2. replace the root val to target node val 5-3. change the key to targe node val, do removeNode for right subtree
6. return the processed root

# 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 find_successor(root):
            return root if not root.left else find_successor(root.left)
        if not root:
            return root
        if key > root.val:
            root.right = self.deleteNode(root.right, key)
        elif key < root.val:
            root.left = self.deleteNode(root.left, key)
        else:
            if not root.right:
                return root.left
            if not root.left:
                return root.right
            successor = find_successor(root.right)
            root.val = new_key = successor.val
            root.right = self.deleteNode(root.right, new_key)
        return root