LogoKode$word

LeetCode 450: Delete Node in a BST – Java Optimized Recursive Solution with Dry Run

Learn how to solve LeetCode 450 Delete Node in a BST using an optimized BST deletion approach in Java. Includes intuition, brute force approach, recursive BST logic, dry run, complexity analysis, interview explanation, and common mistakes.

Krishna Shrivastava
0 views
LinkedInGithubX
0
0
BSTJavaBinary Search TreeLeetCodeTreeRecursionMedium
LeetCode 450: Delete Node in a BST – Java Optimized Recursive Solution with Dry Run
Listen to articleAudio version
Ad
Advertisement

Introduction

The Delete Node in a BST problem is one of the most important Binary Search Tree interview questions because it combines:

  1. BST traversal
  2. Tree restructuring
  3. Recursive thinking
  4. Node replacement logic
  5. Tree manipulation

Unlike searching or insertion, deletion is slightly more complex because we must maintain BST properties after removing a node.

This problem is frequently asked in coding interviews and online assessments.

Problem Link

🔗 LeetCode 450 – Delete Node in a BST

Problem Statement

Given:

  1. The root of a Binary Search Tree
  2. A key value

Delete the node containing the key while preserving BST properties.

Return the updated BST root.

BST Property Reminder

In a Binary Search Tree:

Left subtree -> smaller values
Right subtree -> greater values

After deletion:

  1. Tree must still remain a valid BST.

Example 1

Input

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

Output

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

Visualization

Before deletion:

5
/ \
3 6
/ \ \
2 4 7

After deleting 3:

5
/ \
4 6
/ \
2 7

Key Deletion Cases

BST deletion has 3 important cases.

Case 1: Node Has No Child

Simply remove the node.

Case 2: Node Has One Child

Replace the node with its child.

Case 3: Node Has Two Children

This is the tricky part.

We:

  1. Find inorder predecessor or successor
  2. Replace node
  3. Reconnect subtrees properly

Intuition

Suppose we want to delete:

3

from:

5
/ \
3 6
/ \
2 4

Since node 3 has:

  1. Left child
  2. Right child

we cannot directly delete it.

Instead:

  1. Attach right subtree to rightmost node of left subtree
  2. Return left subtree as replacement

This preserves BST ordering.

Brute Force Approach

Idea

  1. Store inorder traversal
  2. Remove target node
  3. Rebuild BST

Why Brute Force is Bad

Problems:

  1. Extra memory usage
  2. Rebuilding tree is expensive
  3. Unnecessary traversal

Brute Force Complexity

Time Complexity

O(N)

Space Complexity

O(N)

Optimized BST Deletion Approach

Use BST properties to:

  1. Search efficiently
  2. Modify only required nodes
  3. Preserve tree structure

Java Solution

class Solution {

public TreeNode deleteNode(TreeNode root, int key) {

if(root == null)
return root;

if(root.val == key)
return solve(root);

TreeNode originalRoot = root;

while(root != null) {

if(root.val > key) {

if(root.left != null && root.left.val == key) {

root.left = solve(root.left);

} else {

root = root.left;
}

} else {

if(root.right != null && root.right.val == key) {

root.right = solve(root.right);

} else {

root = root.right;
}
}
}

return originalRoot;
}

public TreeNode solve(TreeNode root) {

if(root.left == null)
return root.right;

if(root.right == null)
return root.left;

TreeNode rightChild = root.right;

TreeNode leftChild = asright(root.left);

leftChild.right = rightChild;

return root.left;
}

public TreeNode asright(TreeNode root) {

if(root.right == null)
return root;

return asright(root.right);
}
}

How This Solution Works

The main logic happens inside:

solve(root)

This function deletes the node safely.

Understanding solve()

Case 1

If:

root.left == null

return right subtree.

Case 2

If:

root.right == null

return left subtree.

Case 3

If both children exist:

  1. Save right subtree
  2. Find rightmost node in left subtree
  3. Attach right subtree there
  4. Return left subtree

Why Rightmost Node?

Because:

Rightmost node of left subtree

is the:

largest node smaller than root

This maintains BST ordering perfectly.

Dry Run

Input

5
/ \
3 6
/ \ \
2 4 7

key = 3

Step 1

Search node:

3

Step 2

Node has:

  1. Left child = 2
  2. Right child = 4

Step 3

Find rightmost node in left subtree.

Rightmost node:

2

Step 4

Attach right subtree:

2.right = 4

Step 5

Return left subtree:

2

Updated BST becomes valid.

Time Complexity Analysis

Best Case

O(log N)

Balanced BST.

Worst Case

O(N)

Skewed BST.

Space Complexity

Recursive Helper

O(H)

where:

H = tree height

Alternative Recursive Approach

Another common method:

  1. Replace node with inorder successor
  2. Delete successor recursively

This approach is also interview friendly.

Interview Explanation

In interviews explain:

When deleting a node with two children, we preserve BST properties by connecting the right subtree to the rightmost node of the left subtree.

This demonstrates:

  1. BST restructuring knowledge
  2. Tree manipulation skills
  3. Recursive reasoning
  4. Pointer management

Common Mistakes

1. Forgetting BST Property

Deletion should not break ordering.

2. Losing Subtrees

Always reconnect children carefully.

3. Incorrect Node Replacement

Many candidates replace node incorrectly.

4. Not Handling Null Cases

Always check:

root == null

properly.

FAQs

Q1. Why is BST deletion difficult?

Because tree structure must remain valid after removal.

Q2. Why use rightmost node of left subtree?

It is the largest smaller value.

Perfect replacement candidate.

Q3. Can we use inorder successor instead?

Yes.

Both predecessor and successor approaches work.

Q4. What is deletion complexity?

Balanced BST:

O(log N)

Worst case:

O(N)

Related BST Problems

Practice these next:

  1. Insert into BST
  2. Search in BST
  3. Validate BST
  4. Lowest Common Ancestor in BST
  5. Kth Smallest Element in BST
  6. Inorder Successor in BST

Conclusion

Delete Node in BST is one of the most important BST interview problems because it teaches:

  1. Tree restructuring
  2. Recursive manipulation
  3. Pointer handling
  4. BST property maintenance

The key insight is:

When deleting a node with two children, reconnect subtrees carefully so BST ordering remains valid.

Mastering this problem makes advanced BST operations significantly easier.

Related Articles

Inorder Successor in BST – Java Optimized BST Solution with Dry Run

Inorder Successor in BST – Java Optimized BST Solution with Dry Run

Learn how to solve the GFG Inorder Successor in BST problem using optimized BST traversal in Java. Includes brute force approach, recursive BST solution, intuition, dry run, complexity analysis, interview tips, and common mistakes.

Read Article
LeetCode 145: Binary Tree Postorder Traversal – Java Recursive & Iterative Solution Explained

LeetCode 145: Binary Tree Postorder Traversal – Java Recursive & Iterative Solution Explained

Learn how to solve LeetCode 145 Binary Tree Postorder Traversal using Recursive and Iterative approaches in Java. Includes traversal intuition, stack-based solution, dry run, complexity analysis, interview explanation, and common mistakes.

Read Article
LeetCode 98: Validate Binary Search Tree – Java DFS Recursive Solution Explained

LeetCode 98: Validate Binary Search Tree – Java DFS Recursive Solution Explained

Learn how to solve LeetCode 98 Validate Binary Search Tree using recursion and min/max bounds in Java. Includes BST intuition, brute force approach, optimized DFS solution, dry run, complexity analysis, interview explanation, and common mistakes.

Read Article
Ceil in BST – Java Recursive Binary Search Tree Solution with Dry Run

Ceil in BST – Java Recursive Binary Search Tree Solution with Dry Run

Learn how to solve the Ceil in BST problem using an optimized recursive BST approach in Java. Includes intuition, brute force method, optimized recursion, dry run, time complexity, interview explanation, and common mistakes.

Read Article
Ai Assistant Kas