Delete Node in a BST

This problem involves deleting a node with a given key from a Binary Search Tree (BST) while maintaining the BST properties. Let's explore both a naive and an optimized approach.

1. Naive Approach (Brute Force)

The simplest approach involves:

1. Search: Traverse the tree to find the node to be deleted.
2. Deletion:
   • If the node is a leaf, simply remove it.
   • If the node has one child, replace the node with its child.
   • If the 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, and then delete the successor/predecessor node.

Code Example (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
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        
        # Node with two children: Get the inorder successor
        min_node = root.right
        while min_node.left:
            min_node = min_node.left
        
        root.val = min_node.val
        root.right = deleteNode(root.right, root.val)
    
    return root

• Time Complexity: O(n) in the worst case (skewed tree), where n is the number of nodes.
• Space Complexity: O(h) due to recursion stack, where h is the height of the tree. In the worst case, h can be n.

2. Optimized Approach

The optimized approach aims to maintain the O(height) complexity by ensuring that the tree traversal is proportional to the height of the tree.

The algorithm remains the same as the naive approach, but the key is to ensure that in a balanced BST, the height remains logarithmic with the number of nodes, i.e., O(log n).

Code Example (Python):

The code remains the same as above, but the performance characteristics change if the tree is balanced.

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
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        
        # Node with two children: Get the inorder successor
        min_node = root.right
        while min_node.left:
            min_node = min_node.left
        
        root.val = min_node.val
        root.right = deleteNode(root.right, root.val)
    
    return root

• Time Complexity: O(h), where h is the height of the tree. In a balanced BST, h = O(log n). In the worst case (skewed tree), h = O(n).
• Space Complexity: O(h) due to the recursion stack. In a balanced BST, this is O(log n). In the worst case, O(n).

3. Edge Cases

• Empty Tree: If the root is None, return None.
• Key Not Found: If the key is not in the tree, the original tree should be returned unchanged.
• Deleting Root Node: The algorithm should correctly handle deleting the root node.
• Node with No Children: Handles removal of leaf nodes.
• Node with One Child: Handles cases where the node has only a left or right child.
• Node with Two Children: Properly finds either the inorder successor or predecessor and maintains BST properties.

4. Summary

Category	Naive Approach	Optimized Approach
Time Complexity	O(n)	O(h)
Space Complexity	O(h)	O(h)
Tree Type	Any BST	Balanced BST
Implementation	Straightforward	Straightforward

The optimal solution offers a time complexity of O(h), making it more efficient for balanced BSTs. However, in the worst-case scenario (skewed tree), both approaches degrade to O(n).