Delete Node in a BST

Problem Description

Given the 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.

Naive Approach

1. Search: Traverse the tree to find the node with the target key.
2. Deletion:
   • If the node is a leaf node, 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 value in the right subtree) or inorder predecessor (maximum value in the left subtree), replace the node's value with the successor/predecessor's value, and then delete the successor/predecessor node.

Optimal Approach

The optimal approach is essentially a refined version of the naive approach, focusing on an efficient implementation, particularly for the case where the node to be deleted has two children.

1. Search: Same as the naive approach, traverse the tree to find the node with the target key.
2. Deletion:
   • Case 1: Node is a leaf node:
     • Simply remove the node by setting the corresponding parent's child pointer to null.
   • Case 2: Node has one child:
     • Bypass the node by updating the parent's child pointer to point to the node's child.
   • Case 3: Node has two children:
     • Find the inorder successor (minimum value in the right subtree).
     • Replace the node's value with the inorder successor's value.
     • Delete the inorder successor from the right subtree. Because the inorder successor is the minimum value in the right subtree, it can have at most a right child, simplifying the deletion.

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, perform deletion
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            } else {
                // Node has two children
                TreeNode inorderSuccessor = findMin(root.right);
                root.val = inorderSuccessor.val;
                root.right = deleteNode(root.right, inorderSuccessor.val);
            }
        }

        return root;
    }

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

Big O 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). In the best-case scenario (balanced tree), H is log(N).
• Space Complexity: O(H) due to the recursive call stack. In a balanced tree, this would be O(log N), but in a skewed tree, it could be O(N).

Edge Cases

• Empty Tree: If the root is null, return null.
• Key Not Found: If the key is not present in the tree, the tree remains unchanged, return the root.
• Root Node Deletion: If the node to be deleted is the root, handle the case where the root has zero, one, or two children.