Delete Node in a BST

Medium Top 250

Associated Patterns

Interviewed At (Company Tags)

GoogleAmazonMicrosoftMeta

Problem Description

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two steps:

Search for a node to remove.
If the node is found, delete the node.

Examples

Example 1:

Input: root = [5,3,6,2,4,null,7], key = 3 Output: [5,4,6,2,null,null,7] Explanation: Given key to delete is 3. So we find the node with value 3 and delete it. One valid answer is [5,4,6,2,null,null,7], shown in the above image. Another valid answer is [5,2,6,null,4,null,7].

Example 2:

Input: root = [5,3,6,2,4,null,7], key = 0 Output: [5,3,6,2,4,null,7] Explanation: The tree does not contain a node with value = 0.

Constraints

The number of nodes in the tree is in the range [0, 10⁴].
-10⁵ <= Node.val <= 10⁵
Each node has a unique value.
root is a valid binary search tree.
-10⁵ <= key <= 10⁵

BST Search and Successor Swap

Deleting a node from a BST requires restructuring the tree to preserve BST properties. There are three cases when the target node is found:

Node has no children (Leaf node): Simply return null.
Node has one child: Return that child (node.left or node.right) to the parent link.
Node has two children: Find the inorder successor (the smallest node in its right subtree). Overwrite the target node’s value with the successor’s value, then recursively delete the successor from the right subtree.

Solution 1: Recursive Node Deletion

Search the BST recursively, replacing target node values with their inorder successors if they have two children.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

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 {
            // Node found: Case 1 & 2 (0 or 1 children)
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }

            // Case 3 (2 children): Find inorder successor (min in right subtree)
            TreeNode successor = findMin(root.right);
            root.val = successor.val; // overwrite value
            root.right = deleteNode(root.right, successor.val); // delete successor node
        }
        return root;
    }

    private TreeNode findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        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:
            # Node found: Case 1 & 2 (0 or 1 children)
            if not root.left:
                return root.right
            elif not root.right:
                return root.left
                
            # Case 3 (2 children): Find inorder successor
            successor = root.right
            while successor.left:
                successor = successor.left
                
            root.val = successor.val  # overwrite value
            root.right = self.deleteNode(root.right, successor.val)  # delete successor node
            
        return root

/**
 * 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 {
private:
    TreeNode* findMin(TreeNode* node) {
        while (node->left) {
            node = node->left;
        }
        return node;
    }

public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) return nullptr;

        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) {
                TreeNode* temp = root->right;
                delete root;
                return temp;
            } else if (!root->right) {
                TreeNode* temp = root->left;
                delete root;
                return temp;
            }

            TreeNode* successor = findMin(root->right);
            root->val = successor->val;
            root->right = deleteNode(root->right, successor->val);
        }
        return root;
    }
};

Complexity Analysis

Time Complexity: O(h) where h is the tree height. Finding the node takes O(h) and finding its successor takes at most O(h).
Space Complexity: O(h) auxiliary space due to the recursion call stack.

Where It Breaks

If we must delete elements from a tree structure containing duplicates, simple unique-key binary search paths do not work, and we must perform range deletions.

Common Mistakes

Incorrect pointer mapping: Assigning root.left to root.right directly during Case 3, which drops the entire left subtree and breaks BST rules.
Memory leaks: In C++, forgetting to delete the removed node pointers, leading to memory leaks.