Delete Node in a BST

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

1. Search for a node to remove.
2. If the node is found, delete the node.

Example 1:

Input: root = [5,3,6,2,4,null,7], key = 3 Output: [5,4,6,2,null,null,7] Explanation: Given key to delete is 3. So we find the node with value 3 and delete it. One valid answer is [5,4,6,2,null,null,7], shown in the above BST. Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.

Example 2:

Input: root = [5,3,6,2,4,null,7], key = 0 Output: [5,3,6,2,4,null,7] Explanation: The tree does not contain a node with value = 0.

Example 3:

Input: root = [], key = 0 Output: []

Constraints:

The number of nodes in the tree is in the range [0, 10^4]. -10^5 <= Node.val <= 10^5 Each node has a unique value. root is a valid binary search tree. -10^5 <= key <= 10^5

Follow up: Could you solve it with time complexity O(height of tree)?

## Deleting a Node in a BST

This problem focuses on how to delete a node with a given key from a Binary Search Tree (BST) while maintaining the BST properties.

### Algorithm

1.  **Search for the Node:** Traverse the tree to find the node with the key to be deleted.
2.  **Deletion Cases:**
    *   **Node has no children (Leaf Node):** Simply remove the node.
    *   **Node has one child:** Replace the node with its child.
    *   **Node has two children:** Find the inorder successor (minimum value in the right subtree) or inorder predecessor (maximum value in the left subtree) of the node. Replace the node's value with the inorder successor/predecessor's value, and then delete the inorder successor/predecessor.

### Code Implementation (Python)

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

def deleteNode(root: TreeNode, key: int) -> TreeNode:
    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
        
        # Case 1: No child
        if not root.left and not root.right:
            return None
        
        # Case 2: One child
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        
        # Case 3: Two children
        # Find inorder successor (min of right subtree)
        def minValueNode(node):
            current = node
            while(current.left is not None):
                current = current.left
            return current
        
        temp = minValueNode(root.right)
        root.val = temp.val
        root.right = deleteNode(root.right, temp.val)
            
    return root

Code Implementation (Java)

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }

        if (key < root.val) {
            root.left = deleteNode(root.left, key);
        } else if (key > root.val) {
            root.right = deleteNode(root.right, key);
        } else {
            // Node found

            // Case 1: No child
            if (root.left == null && root.right == null) {
                return null;
            }

            // Case 2: One child
            if (root.left == null) {
                return root.right;
            }
            if (root.right == null) {
                return root.left;
            }

            // Case 3: Two children
            // Find inorder successor (min of right subtree)
            TreeNode temp = minValueNode(root.right);
            root.val = temp.val;
            root.right = deleteNode(root.right, temp.val);
        }

        return root;
    }

    private TreeNode minValueNode(TreeNode node) {
        TreeNode current = node;
        while (current.left != null) {
            current = current.left;
        }
        return current;
    }
}

Big O Runtime Analysis

• Time Complexity: O(H), where H is the height of the tree. In the worst-case scenario (skewed tree), H can be equal to N (number of nodes), resulting in O(N) time complexity. However, for a balanced BST, H is log(N), resulting in O(log N) time complexity.
  • The algorithm traverses the tree to find the node to be deleted. This traversal takes O(H) time.
  • Finding the inorder successor (in the case of a node with two children) also takes O(H) time.

Big O Space Usage Analysis

• Space Complexity: O(H), where H is the height of the tree, due to the recursive call stack. In the worst-case scenario (skewed tree), H can be equal to N, resulting in O(N) space complexity. For a balanced BST, the space complexity is O(log N).
  • The recursive calls to deleteNode create a call stack that grows proportionally to the height of the tree.

Edge Cases

1. Empty Tree: If the root is None, return None.
2. Key Not Found: If the key is not in the tree, return the original tree.
3. Deleting the Root Node: Handle the case where the node to be deleted is the root node.
4. Duplicate Keys: If there are duplicate keys, make sure the correct node is deleted.

Alternative Approaches

• Iterative Approach: The algorithm can be implemented iteratively using a stack to avoid recursion, reducing the space complexity to O(1) in the average case, but the code will be much harder to read.
• Using Inorder Predecessor: Instead of finding the inorder successor, we can find the inorder predecessor (maximum value in the left subtree).