Technical Interview Question: Binary Search Trees - Delete Node in a BST

Given a binary search tree (BST), write a function to delete a specific node from the tree. You are required to implement the deleteNode function and handle all possible cases of node deletion.

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public TreeNode deleteNode(TreeNode root, int key) {
    // Your implementation here
}

Answer:

To delete a node from a binary search tree, we need to consider three possible cases:

1. Node with no children (Leaf Node): Simply remove the node from the tree.
2. Node with one child: Link the parent of the node to the child of the node.
3. Node with two children: Find the successor or predecessor node, swap its value with the node to be deleted, and then delete the successor or predecessor node.

Here's a step-by-step explanation of the deleteNode function:

public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) {
        return null; // If the tree is empty
    }

    if (key < root.val) {
        root.left = deleteNode(root.left, key); // Recursively delete from the left subtree
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key); // Recursively delete from the right subtree
    } else {
        if (root.left == null) {
            return root.right; // Case 1: Node with no left child or no children
        } else if (root.right == null) {
            return root.left; // Case 2: Node with no right child
        }
        // Case 3: Node with two children
        TreeNode successor = findSuccessor(root.right); // Find the successor
        root.val = successor.val; // Replace the node's value with that of the successor
        root.right = deleteNode(root.right, successor.val); // Delete the successor
    }
    return root; // Return the updated node
}

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

In the above implementation, we recursively search for the node to be deleted, handle the three cases of deletion, and find the successor node for the case when the node has two children. This ensures that the binary search tree is correctly maintained after the deletion operation.

This solution has a time complexity of O(log n) in the average case (where n is the number of nodes in the tree) and O(n) in the worst case, and a space complexity of O(log n) due to the recursive calls.