Vansh Aggarwal

Posted on Apr 5

LeetCode Solution: 450. Delete Node in a BST

#leetcode #dsa #programming #tutorial

Conquering BST Deletion: A Beginner's Guide to LeetCode 450

Hey amazing developers! Vansh2710 here, ready to tackle another classic LeetCode problem. Today, we're diving into the sometimes-tricky world of Binary Search Tree (BST) deletion. Specifically, we're taking on LeetCode 450: Delete Node in a BST.

Don't let the "deletion" part scare you! While it might seem intimidating at first, we'll break it down step-by-step, making it super clear and manageable. Think of it as a puzzle with a few distinct pieces – once you understand each piece, the whole picture becomes simple.

The Problem Explained: Deleting a Node from a BST

Imagine you have a phone directory (a BST!). Each entry (node) has a name (value). You want to remove an old contact (a key) from this directory while making sure it remains sorted alphabetically (maintaining the BST property).

That's essentially what LeetCode 450 asks us to do:
Given the root of a Binary Search Tree and a key (the value of the node you want to delete):

Search: First, locate the node that contains the key.
Delete: If the node is found, remove it. The tricky part is ensuring that after deletion, the tree remains a valid BST! If the node isn't found, simply return the original tree.

What is a BST, again?
A Binary Search Tree is a special type of binary tree where for every node:

All values in its left subtree are less than the node's value.
All values in its right subtree are greater than the node's value. This property makes searching, insertion, and deletion very efficient!

Let's look at an example:

Example 1:
Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]

Initially:

We want to delete 3. Notice how 4 takes its place to maintain the BST property ( 4 is greater than 2 and less than 5).

After deleting 3 and replacing with 4:

(Another valid answer could have 2 taking 3's place!)

The key takeaway here is that when you remove a node, you need to find a suitable replacement that keeps the whole tree "sorted."

Intuition: The "Aha!" Moment for Deletion

The core idea behind BST deletion is maintaining its fundamental property. When you remove a node, its children (if any) can't just float in space. They need to be reattached in a way that preserves the BST order.

The "aha!" moment comes from realizing there are three main scenarios when you find the node to delete:

It's a leaf node (no children): This is the easiest! Just remove it. No children to worry about.
It has one child: The child can simply take the place of the deleted node. If you delete node X which has only a left child L, then L becomes the new child of X's parent. The BST property holds because all nodes in L's subtree are still less than X's parent (if X was a left child) or greater (if X was a right child).
It has two children: This is the trickiest part! You can't just pick one child, as the other would be lost. Here's where we get clever:
- To maintain the BST property, the replacement node must be greater than all nodes in the left subtree and less than all nodes in the right subtree.
- The perfect candidates for this are either the smallest node in the right subtree (also known as the in-order successor) or the largest node in the left subtree (the in-order predecessor).
- If we replace the deleted node's value with its in-order successor's value, the BST property is preserved. Then, we simply delete that successor from its original position in the right subtree (which will be one of the easier cases: a leaf or a node with one child, specifically a right child).

We can use a recursive approach for this. Why? Because searching for the node and then potentially deleting a replacement node (if it has two children) are both operations that can be naturally handled by recursion, similar to how we traverse BSTs.

Approach: Step-by-Step Logic

Let's translate that intuition into a concrete algorithm:

Our deleteNode(root, key) function will work recursively:

Base Case:
- If root is nullptr (the tree is empty or we've searched past a leaf), the key isn't found. Return nullptr.
Search Phase:
- If key < root->val: The node we want to delete must be in the left subtree. Recursively call root->left = deleteNode(root->left, key).
- If key > root->val: The node we want to delete must be in the right subtree. Recursively call root->right = deleteNode(root->right, key).
Deletion Phase (when key == root->val): We found the node to delete! Now, we handle the three cases:

*   **Case 1: Node has no children (Leaf Node)**
    *   Simply delete the `root` node and return `nullptr` to its parent, effectively removing it from the tree.

*   **Case 2: Node has one child**
    *   If `root->left` is `nullptr` (only a right child): Store `root->right` in a temporary variable, delete `root`, and return the `temp` node. The right child takes its parent's place.
    *   If `root->right` is `nullptr` (only a left child): Store `root->left` in a temporary variable, delete `root`, and return the `temp` node. The left child takes its parent's place.

*   **Case 3: Node has two children**
    *   This is the most involved part. We need to find the in-order successor.
    *   **Find Successor:** Traverse to the right child of the current `root`, then keep going left as far as possible. This will give you the smallest node in the right subtree. Let's call this `successor`.
    *   **Replace Value:** Copy `successor->val` into `root->val`. Now, the current node `root` has the value of its successor.
    *   **Delete Successor:** The `successor` node is now duplicated. We need to remove its original position. Recursively call `root->right = deleteNode(root->right, successor->val)`. This will remove the `successor` from the right subtree, which will be an easier deletion case (either a leaf or a node with one right child).

Return root: After any modifications (or if no deletion happened), always return the current root back to its parent. This is crucial for correctly rebuilding the tree structure in the recursive calls.

The Code

Here's the C++ implementation following our approach.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        // Base Case: If the tree is empty or key not found
        if (root == nullptr){
            return nullptr;
        }

        // Search Phase: Traverse the BST to find the node
        if(key < root->val){
            // Key is smaller, go to the left subtree
            root -> left  = deleteNode(root->left, key);
        }
        else if(key > root->val){
            // Key is larger, go to the right subtree
            root->right = deleteNode(root->right, key);
        }
        else{ // key == root->val: Node to be deleted found!
            // Case 1: Node has no children (it's a leaf)
            if(root->left == nullptr && root->right == nullptr){
                delete root; // Free memory
                return nullptr; // This node is now gone
            }
            // Case 2: Node has only one child
            else if(root->left == nullptr){ // Only right child exists
                TreeNode* temp = root->right; // Store the right child
                delete root; // Delete the current node
                return temp; // Replace current node with its right child
            }
            else if(root->right == nullptr){ // Only left child exists
                TreeNode* temp = root->left; // Store the left child
                delete root; // Delete the current node
                return temp; // Replace current node with its left child
            }
            // Case 3: Node has two children
            else{
                // Find the in-order successor (smallest node in the right subtree)
                TreeNode* successor = root->right;
                while(successor->left != nullptr){
                    successor = successor->left;
                }

                // Replace the value of the current node with the successor's value
                root->val = successor->val;

                // Recursively delete the successor from the right subtree
                // The successor will either be a leaf or have only a right child,
                // making its deletion simple.
                root->right = deleteNode(root->right, successor->val);
            }
        }
        // Return the (potentially updated) root of the current subtree
        return root;
    }
};

Time & Space Complexity Analysis

Let's break down how efficient our solution is:

Time Complexity: O(H)
- H is the height of the BST.
- In the worst case (a skewed tree, like a linked list), H can be N (number of nodes). In the best case (a balanced tree), H is log N.
- Why O(H)?
  - The search phase involves traversing down the tree, at most H levels.
  - If the node has two children, finding the successor also involves traversing down the right subtree, at most H levels.
  - The recursive call to delete the successor also follows a path down the tree, again at most H levels.
  - All these operations combined are proportional to the height of the tree.
Space Complexity: O(H)
- This is due to the recursion call stack. In the worst case, if the tree is highly skewed, the recursion depth can be N. For a balanced tree, it's log N.

This solution perfectly meets the follow-up requirement of solving it with time complexity O(height of tree)!

Key Takeaways

Recursive Thinking is Your Friend: BST problems often lend themselves beautifully to recursion. Thinking about how to solve a subproblem and combine results is key.
Three Deletion Cases: The heart of BST deletion lies in distinguishing and handling leaf nodes, nodes with one child, and nodes with two children separately.
In-order Successor/Predecessor: For nodes with two children, the in-order successor (smallest in right subtree) or predecessor (largest in left subtree) is your go-to replacement to maintain the BST property.
Memory Management: In C++, remember to delete nodes to prevent memory leaks, especially when you are freeing up a node's memory.

BST deletion is a foundational concept in data structures. Mastering it gives you a deeper understanding of how trees work and how to manipulate them efficiently. Keep practicing, and you'll be a BST pro in no time!

Happy coding!

Author Account: Vansh2710
Time Published: 2026-04-05 22:06:35

DEV Community