LeetCode · #450

Delete Node in a BST Solution

BST deletion is all about handling the three structural cases cleanly while preserving the ordering invariant.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #450

🏗️

Pattern

BST delete — three-case handling

Delete a node with the given key from the BST and return the updated root. The BST ordering must still be valid afterward.

Core cases

 1. Leaf node          → remove it 2. One child          → return that child 3. Two children       → replace with inorder successor, then delete successor 

Section Two · Approach 1

Rebuild Entire Tree

You could collect all values except the target and rebuild a BST from scratch.

Problem: That turns a local structural update into a full reconstruction. BST delete should only touch one search path plus maybe the inorder successor path.

Section Three · Approach 2

Recursive Delete — O(h)

First search for the target like a normal BST operation. Once found, handle one of the three structural cases.

💡 Mental model: Removing a leaf is easy. Removing a node with one child means splicing that child up. Removing a node with two children means borrowing the next larger value — the inorder successor — because it is the safest replacement.

Why inorder successor works

The successor is the smallest value in the right subtree.
So it is larger than everything in the left subtree.
And smaller than everything else remaining in the right subtree.
That makes it a valid replacement for the deleted node.

Important:

After copying the successor value, you still must delete the successor from the right subtree.
Otherwise the value appears twice.

Section Four · Trace

Visual Walkthrough

Delete node with two children

Section Five · Implementation

Code — Java & Python

Java — recursive delete

 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 {
if (root.left == null) return root.right;
if (root.right == null) return root.left;
TreeNode successor = findMin(root.right);
            root.val = successor.val;
            root.right = deleteNode(root.right, successor.val);
        }
return root;
    }
private TreeNode findMin(TreeNode node) {
while (node.left != null) node = node.left;
return node;
    }
}

Python — recursive delete

 class Solution:
def deleteNode(self, root, key: int):
if not root:
return None if key < root.val:
            root.left = self.deleteNode(root.left, key)
elif key > root.val:
            root.right = self.deleteNode(root.right, key)
else:
if not root.left:
return root.right
if not root.right:
return root.left

            successor = root.right
while successor.left:
                successor = successor.left
            root.val = successor.val
            root.right = self.deleteNode(root.right, successor.val)
return root

Section Six · Analysis

Complexity Analysis

Approach	Time	Space
Rebuild tree	O(n)	O(n)
BST delete	O(h)	O(h)

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Why it matters
Delete missing key	Return the tree unchanged after reaching null.
Delete root	The returned subtree root might become the new overall root.
Delete node with two children	This is the only case requiring successor or predecessor replacement.

⚠ Common Mistake: Copying the successor value into the node but forgetting to remove the successor node afterward. That leaves a duplicate value in the BST.

← Back to BST problems

LearningTree

LC 450 · Delete Node in a BST — Solution & Explanation | DSA Guide