# 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: TreeNode, key: int) -> TreeNode:
        # find the node first
        if not root:
            return None

        node = root
        parent_node = root
        isLeft = False

        while node and node.val != key:
            parent_node = node
            if node.val > key:
                isLeft = True
                node = node.left
            else:
                isLeft = False
                node = node.right

        if not node:  # node not found
            return root

        # case 1: node has no children
        if not node.right and not node.left:
            if node == root:
                return None
            elif isLeft:
                parent_node.left = None
            else:
                parent_node.right = None
        # case 2: node has 1 child
        elif node.right and not node.left:
            if node == root:
                root = node.right
            elif isLeft:
                parent_node.left = node.right
            else:
                parent_node.right = node.right
        elif node.left and not node.right:
            if node == root:
                root = node.left
            elif isLeft:
                parent_node.left = node.left
            else:
                parent_node.right = node.left
        # case 3: node has 2 children
        else:
            successor = node.right
            successor_parent = node
            while successor.left:
                successor_parent = successor
                successor = successor.left

            if successor != node.right:
                successor_parent.left = successor.right
                successor.right = node.right
            else:
                successor_parent.right = successor.right

            if node == root:
                root.val = successor.val
            elif isLeft:
                parent_node.left.val = successor.val
            else:
                parent_node.right.val = successor.val

        return root

