Delete a Node in a Binary Search Tree (BST)

Hey fellow developers 👋

Welcome back to our DSA learning series!

This series is all about picking problems that every beginner finds confusing at first — and breaking them down slowly and logically. We are students ourselves, and we know how overwhelming DSA can feel if you jump straight into the code without understanding why something works.

In this post, we are going to talk about a problem that really helps you understand how Binary Search Trees work beneath the surface:

Deleting a node from a Binary Search Tree (BST).

At first, it may feel a bit complicated — especially when the node has children.
But once you slow down and reason through each case, the logic becomes surprisingly neat and structured.

Let us walk through it step by step.

---

Quick Reminder: What Makes a BST Special?

In a Binary Search Tree:

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

This ordering is exactly what allows us to efficiently search, insert, and delete.

---

Problem Statement

You are given the root of a BST and a value key.
Your job is to delete the node with that key (if it exists) and return the updated tree.

The twist: Deletion must be handled in a way that keeps the tree a valid BST.

---

Finding the Node First

Before deleting anything, we first locate the node:

• If key < root.val → go left
• If key > root.val → go right
• If equal → this is the node we want to delete

---

The Three Deletion Cases

Once we find the node, there are only three possible scenarios.

Case 1: Node Has No Children (Leaf Node)

This is the easiest case. If the node has no left and right child, we simply remove it.
return null;

Case 2: Node Has One Child

If the node has only one child, we replace it with that child.

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

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

This is where most students get stuck — but it follows a very clean idea. We cannot just delete the node, because both sides still hold valid subtrees.

So we do this:

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;

        // searching 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
            // 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

What makes this problem powerful is not the code — it is the structured way of thinking:

• Understand the BST property
• Identify the node
• Handle each deletion case calmly
• Preserve the structure

Once this mental model clicks, most tree problems suddenly feel more manageable.

If you try implementing this yourself a couple of times, you will notice the logic becoming second nature.

Happy coding — and see you in the next article!