class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return None

        if key < root.val:
            root.left = self.deleteNode(root.left, key)
            return root
        elif key > root.val:
            root.right = self.deleteNode(root.right, key)
            return root

        return self.mergeTrees(root.left, root.right)

    def mergeTrees(
        self,
        left: Optional[TreeNode],
        right: Optional[TreeNode],
    ) -> Optional[TreeNode]:
        if not left or not right:
            return left or right

        if not left.right:
            left.right = right
            return left
        if not right.left:
            right.left = left
            return right

        right, smallest_node = self.popSmallestNode(right)
        smallest_node.left = left
        smallest_node.right = right
        return smallest_node

    def popSmallestNode(
        self,
        root: TreeNode,
    ) -> Tuple[Optional[TreeNode], TreeNode]:
        if not root.left:
            rr = root.right
            root.right = None
            return (rr, root)

        new_left, smallest_node = self.popSmallestNode(root.left)
        root.left = new_left
        return (root, smallest_node)