Delete Node in a BST

Link: LeetCode - Delete Node in a BST

Problem Statement

Given the root of a binary search tree and a key, delete the node with the given key in the BST.
Return the root of the modified BST.

BST must retain its properties after deletion.

Example

Input:

root = [5,3,6,2,4,null,7], key = 3

Output:

[5,4,6,2,null,null,7]

Constraints

• The number of nodes in the tree is in the range [0, 10⁴].

• -10⁵ <= Node.val <= 10⁵

• All node values are unique.

• -10⁵ <= key <= 10⁵

Intuition

In a Binary Search Tree, deletion can be broken into 3 cases:

1. Node not found – return root.

2. Leaf node – directly delete.

3. Node has one child – return that child.

4. Node has two children – replace the node’s value with the inorder successor (smallest in the right subtree), then recursively delete that successor.

Approach: Recursive Deletion

Java Code

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
            if (root.left == null) return root.right;
            else if (root.right == null) return root.left;

            // Node with two children
            TreeNode minNode = findMin(root.right);
            root.val = minNode.val; // Replace value
            root.right = deleteNode(root.right, minNode.val); // Delete successor
        }

        return root;
    }

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

Time and Space Complexity

• Time Complexity: O(H)
  Where H is height of the tree

  • Balanced BST: O(log N)

  • Skewed BST: O(N)

• Space Complexity: O(H) due to recursion stack

Dry Run

Tree:

    5
   / \
  3   6
 / \    \
2   4    7

Key = 3

• 3 == root.left → node to delete has two children (2, 4)

• Inorder successor = 4

• Replace 3 with 4

• Delete 4 in right subtree

Result:

    5
   / \
  4   6
 /      \
2        7

Conclusion

This problem builds intuition for recursion in trees, successor/predecessor logic, and real-world BST operations.