class Solution:
    # time: O(N) worst case, O(height) average
    # space: O(N) worst case, O(height) average
    def delete_node(self, root, value):
        if not root:
            return None
        
        if root.value > value:
            root.left = self.delete_node(root.left, value)
        elif root.value < value:
            root.right = self.delete_node(root.right, value)
        else:
            if not root.left or not root.right:
                # one or no children
                root = root.left or root.right
            else:
                # has both children
                next_biggest = root.right
                while next_biggest.left:
                    next_biggest = next_biggest.left
                root.value = next_biggest.value
                root.right = self.delete_node(root.right, root.value)
        
        return root

