Introduction

Delete Node in BST means:

  • removing node
    from Binary Search Tree
    while maintaining BST rules

BST Property:

Left subtree values < Root value < Right subtree values

Goal:

  • safely remove node
  • preserve BST ordering
  • reconnect subtrees correctly

Example:

 Before Delete:        5
      /   \
     3     6
    / \     \
   2   4     7

Delete:
3

After Delete:
        5
      /   \
     4     6
    /       \
   2         7

Explanation:

4 replaces node 3 because it is inorder successor.

This problem is one of the most important applications of:

DFS Traversal

Constraints

1 <= Number of Nodes <= 10^5

Approach : Recursive BST Deletion

Explanations:

Explanation:

The idea is:

  • locate target node
  • handle deletion cases
  • reconnect BST properly

Deletion Cases:

  1. Leaf node
  2. One child
  3. Two children

Steps:

  1. Visit current node.
  2. Compare deletion key.
  3. Move left or right.
  4. Find target node.
  5. Handle deletion case.
  6. Reconnect subtree.

For two children:

Replace node with inorder successor (minimum in right subtree)

This approach:

  • uses DFS recursion
  • preserves BST ordering

Dry Run

Visit:5
3 < 5
Move left.

Target node:
3

Node has two children.

Find inorder successor:
4

Replace and delete successor.

Practice :

Complexity Analysis :

Time Complexity:- O(h)Explanation :
Only one subtree is traversed during deletion.

Space Complexity:- O(h)
Explanation :
Recursion stack depends on BST height.

Why This Problem is Important

This problem builds the foundation for:

  • BST deletion
  • DFS recursion
  • Ordered tree maintenance
  • Recursive searching
  • Binary search tree analysis

Real-World Applications

BST deletion concepts are used in:

  • Database indexing
  • Search engines
  • Dynamic ordered storage
  • Tree-based caching
  • Memory management systems

Common Beginner Mistakes

  • Incorrect deletion case handling
  • Forgetting inorder successor
  • Breaking BST ordering
  • Wrong subtree reconnection
  • Missing recursive updates

Interview Tip

Interviewers often expect:

  • BST understanding
  • deletion case explanation
  • subtree reconnection logic
  • inorder successor discussion

Always explain:

  • three deletion cases
  • inorder successor replacement
  • BST ordering preservation

Related Questions

  • Insert into BST
  • Validate BST
  • Kth Smallest Element
  • Binary Search Tree
  • Inorder Traversal

Final Takeaway

The Delete Node in BST problem is one of the most important intermediate BST problems.

It teaches:

  • BST deletion
  • DFS recursion
  • subtree reconnection
  • ordered tree maintenance

Understanding this problem builds a strong foundation for:

  •  advanced BST problems
  • tree optimization
  • interview-level algorithms.