Naive Solution: Recursively Search and Replace (O(n) time, O(n) space)

One straightforward approach is to recursively traverse the BST, locate the node with the key to be deleted, and then handle the deletion based on the node's children.

1. Search: Traverse the BST to find the node with the target key. If the key is smaller than the current node's value, go left. If it's larger, go right. If the key matches, proceed to the deletion step.
2. Deletion:
   • Case 1: Node has no children (leaf node): Simply remove the node.
   • Case 2: Node has one child: Replace the node with its child.
   • Case 3: Node has two children: Find the inorder successor (minimum node in the right subtree) or inorder predecessor (maximum node in the left subtree). Replace the node's value with the successor/predecessor's value, then delete the successor/predecessor from its original position.

Big O Analysis:

• Time Complexity: O(n) in the worst case, where n is the number of nodes (if the tree is highly skewed).
• Space Complexity: O(n) in the worst case due to the recursive call stack.

Code (Python):

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def deleteNode(root, key):
    if not root:
        return None

    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        # Node found, perform deletion
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        
        # Node has two children
        # Find inorder successor (minimum in the right subtree)
        successor = find_min(root.right)
        root.val = successor.val
        root.right = deleteNode(root.right, successor.val)

    return root

def find_min(node):
    while node.left:
        node = node.left
    return node

Optimal Solution: Iterative with O(height) Complexity

To achieve O(height) time complexity, where height is the height of the BST, we can use an iterative approach.

1. Search: Iteratively traverse the BST to find the node to delete. Keep track of the parent of the node to be deleted.
2. Deletion:
   • Case 1: Node has no children (leaf node): Update the parent's child pointer to None.
   • Case 2: Node has one child: Update the parent's child pointer to point to the node's child.
   • Case 3: Node has two children: Find the inorder successor (minimum node in the right subtree) or inorder predecessor (maximum node in the left subtree). Replace the node's value with the successor/predecessor's value, then delete the successor/predecessor from its original position. This deletion can be done iteratively, as the successor will have at most one child.

Big O Analysis:

• Time Complexity: O(height) in the average and best case, O(n) in the worst case (skewed tree).
• Space Complexity: O(1) - iterative approach uses constant extra space.

Edge Cases:

• Empty Tree: If the input root is None, return None.
• Key Not Found: If the key is not present in the tree, the tree remains unchanged, so return the original root.
• Deleting the Root: If the node to be deleted is the root node, the logic needs to handle updating the root pointer correctly.

Code (Python):

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def deleteNode(root, key):
    if not root:
        return None

    curr = root
    parent = None

    # Find the node to delete and its parent
    while curr and curr.val != key:
        parent = curr
        if key < curr.val:
            curr = curr.left
        else:
            curr = curr.right

    # Key not found
    if not curr:
        return root

    # Case 1: Node has no children
    if not curr.left and not curr.right:
        if not parent:
            return None  # Deleting the root node
        if curr == parent.left:
            parent.left = None
        else:
            parent.right = None

    # Case 2: Node has one child
    elif not curr.left or not curr.right:
        child = curr.left if curr.left else curr.right
        if not parent:
            return child  # Deleting the root node
        if curr == parent.left:
            parent.left = child
        else:
            parent.right = child

    # Case 3: Node has two children
    else:
        # Find inorder successor (minimum in the right subtree)
        successor = find_min(curr.right)
        curr.val = successor.val
        # Delete the successor (which has at most one child)
        curr.right = deleteNode(curr.right, successor.val)

    return root

def find_min(node):
    while node.left:
        node = node.left
    return node