deleteNode.py

# 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:
        def deleter(node: TreeNode, key: int):
            if not node:
                return node
            
            if node.val > key:
                node.left = deleter(node.left, key)
            elif node.val < key:
                node.right = deleter(node.right, key)
            else:
                # Node to delete, val == key
                # No left child
                if not node.left:
                    return node.right
                # No right child
                if not node.right:
                    return node.left
                
                # Both children are present
                
                # Replace with max value from left subtree or min value from right subtree
                # max value from left subtree
                # - last right leaf
                # min value from left subtree
                # - last left leaf
                max_left = node.left
                while max_left.right:
                    max_left = max_left.right
                
                # Replace value
                node.val = max_left.val
                # Delete node with max value in left sub tree
                node.left = deleter(node.left, max_left.val)
                
            return node
                
        return deleter(root, key)