Delete node in BST

XXX. Delete Node in a BST

Recursion

Binary Search Tree

Problem Statement:

Given a root node of a binary search tree (BST) and a key, delete the node with the given key and ensure the BST properties are maintained. If the key does not exist, return the unchanged BST.

Algorithm:

1. Recursively traverse the tree:
   • If the key is greater than the current node's value, recurse into the right subtree.
   • If the key is smaller, recurse into the left subtree.
2. Once the node to be deleted is found:
   • If the node is a leaf, set it to null.
   • If the node has a right child, replace its value with its in-order successor (smallest value in the right subtree) and recursively delete the successor node.
   • If the node has no right child but has a left child, replace its value with its in-order predecessor (largest value in the left subtree) and recursively delete the predecessor node.
3. Return the updated root.

Complexity:

Time: O(h), where h is the height of the tree | Space: O(h) for the recursion stack.

Java Implementation:

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

        // Traverse the right subtree if the key is greater than the root's value
        if (key > root.val) root.right = deleteNode(root.right, key);
        // Traverse the left subtree if the key is smaller than the root's value
        else if (key < root.val) root.left = deleteNode(root.left, key);
        // Node to delete found
        else {
            // Case 1: Node is a leaf
            if (root.left == null && root.right == null) root = null;
            // Case 2: Node has a right child
            else if (root.right != null) {
                root.val = successor(root); // Replace value with in-order successor
                root.right = deleteNode(root.right, root.val); // Delete the successor
            }
            // Case 3: Node has no right child but has a left child
            else {
                root.val = predecessor(root); // Replace value with in-order predecessor
                root.left = deleteNode(root.left, root.val); // Delete the predecessor
            }
        }
        return root;
    }

    // Helper function to find in-order successor
    public int successor(TreeNode root) {
        root = root.right; // Move one step to the right
        while (root.left != null) root = root.left; // Traverse to the leftmost node
        return root.val;
    }

    // Helper function to find in-order predecessor
    public int predecessor(TreeNode root) {
        root = root.left; // Move one step to the left
        while (root.right != null) root = root.right; // Traverse to the rightmost node
        return root.val;
    }
}