Delete a Node in a Binary Search Tree (BST)

Source: Dev.to

Quick Reminder: What Makes a BST Special?

• All values in the left subtree are smaller than the node.
• All values in the right subtree are greater.

This ordering enables efficient search, insertion, and deletion.

Problem Statement

You are given the root of a BST and a value key.
Delete the node with that key (if it exists) and return the updated tree, ensuring the tree remains a valid BST.

Finding the Node First

• If key root.val → go right.
• If equal → this is the node to delete.

The Three Deletion Cases

Case 1: Node Has No Children (Leaf Node)

Simply remove the node:

return null;

Case 2: Node Has One Child

Replace the node with its sole child.

• Only right child → return root.right;
• Only left child → return root.left;

Case 3: Node Has Two Children (The Interesting One)

1. Find the inorder successor (the smallest value in the right subtree).
2. Copy its value into the current node.
3. Delete that successor node from the right subtree.

Putting It All Together — Code

class Solution {

    // Finds the inorder successor (smallest node in right subtree)
    public static TreeNode inOrderSuccessor(TreeNode root) {
        while (root.left != null) {
            root = root.left;
        }
        return root;
    }

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

        // Search for the node
        if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
        } else {
            // Found the node to delete

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

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

            // Case 3: Two children
            TreeNode successor = inOrderSuccessor(root.right);
            root.val = successor.val;
            root.right = deleteNode(root.right, successor.val);
        }

        return root;
    }
}

Final Thoughts

• Understand the BST property.
• Identify the node to delete.
• Handle each deletion case methodically.
• Preserve the tree’s structure.

Practicing this pattern will make most tree problems feel more manageable. Happy coding!