LeetCodee

450. Delete Node in a BST

Jump to Solution: Python Java C++ JavaScript C#

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 stages:

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

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 BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.

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.

Example 3:

Input: root = [], key = 0
Output: []

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⁵

Solution

Python Solution

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return None
        
        # Search for the node to delete
        if key < root.val:
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:
            root.right = self.deleteNode(root.right, key)
        else:
            # Case 1: Leaf node
            if not root.left and not root.right:
                return None
            # Case 2: Node with only one child
            elif not root.left:
                return root.right
            elif not root.right:
                return root.left
            # Case 3: Node with two children
            else:
                # Find the minimum value in the right subtree
                successor = self.findMin(root.right)
                root.val = successor.val
                root.right = self.deleteNode(root.right, successor.val)
        
        return root
    
    def findMin(self, node: TreeNode) -> TreeNode:
        current = node
        while current.left:
            current = current.left
        return current

Time Complexity: O(h)

Where h is the height of the tree. In the worst case, O(n) for a skewed tree.

Space Complexity: O(h)

For the recursion stack.

Java Solution

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        
        // Search for the node to delete
        if (key < root.val) {
            root.left = deleteNode(root.left, key);
        } else if (key > root.val) {
            root.right = deleteNode(root.right, key);
        } else {
            // Case 1: Leaf node
            if (root.left == null && root.right == null) {
                return null;
            }
            // Case 2: Node with only one child
            else if (root.left == null) {
                return root.right;
            }
            else if (root.right == null) {
                return root.left;
            }
            // Case 3: Node with two children
            else {
                TreeNode successor = findMin(root.right);
                root.val = successor.val;
                root.right = deleteNode(root.right, successor.val);
            }
        }
        
        return root;
    }
    
    private TreeNode findMin(TreeNode node) {
        TreeNode current = node;
        while (current.left != null) {
            current = current.left;
        }
        return current;
    }
}

Time Complexity: O(h)

Where h is the height of the tree. In the worst case, O(n) for a skewed tree.

Space Complexity: O(h)

For the recursion stack.

C++ Solution

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) {
            return nullptr;
        }
        
        // Search for the node to delete
        if (key < root->val) {
            root->left = deleteNode(root->left, key);
        } else if (key > root->val) {
            root->right = deleteNode(root->right, key);
        } else {
            // Case 1: Leaf node
            if (!root->left && !root->right) {
                delete root;
                return nullptr;
            }
            // Case 2: Node with only one child
            else if (!root->left) {
                TreeNode* temp = root->right;
                delete root;
                return temp;
            }
            else if (!root->right) {
                TreeNode* temp = root->left;
                delete root;
                return temp;
            }
            // Case 3: Node with two children
            else {
                TreeNode* successor = findMin(root->right);
                root->val = successor->val;
                root->right = deleteNode(root->right, successor->val);
            }
        }
        
        return root;
    }
    
private:
    TreeNode* findMin(TreeNode* node) {
        TreeNode* current = node;
        while (current->left) {
            current = current->left;
        }
        return current;
    }
};

Time Complexity: O(h)

Where h is the height of the tree. In the worst case, O(n) for a skewed tree.

Space Complexity: O(h)

For the recursion stack.

JavaScript Solution

/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
var deleteNode = function(root, key) {
    if (!root) {
        return null;
    }
    
    // Search for the node to delete
    if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else {
        // Case 1: Leaf node
        if (!root.left && !root.right) {
            return null;
        }
        // Case 2: Node with only one child
        else if (!root.left) {
            return root.right;
        }
        else if (!root.right) {
            return root.left;
        }
        // Case 3: Node with two children
        else {
            const successor = findMin(root.right);
            root.val = successor.val;
            root.right = deleteNode(root.right, successor.val);
        }
    }
    
    return root;
};

function findMin(node) {
    let current = node;
    while (current.left) {
        current = current.left;
    }
    return current;
}

Time Complexity: O(h)

Where h is the height of the tree. In the worst case, O(n) for a skewed tree.

Space Complexity: O(h)

For the recursion stack.

C# Solution

public class Solution {
    public TreeNode DeleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        
        // Search for the node to delete
        if (key < root.val) {
            root.left = DeleteNode(root.left, key);
        } else if (key > root.val) {
            root.right = DeleteNode(root.right, key);
        } else {
            // Case 1: Leaf node
            if (root.left == null && root.right == null) {
                return null;
            }
            // Case 2: Node with only one child
            else if (root.left == null) {
                return root.right;
            }
            else if (root.right == null) {
                return root.left;
            }
            // Case 3: Node with two children
            else {
                TreeNode successor = FindMin(root.right);
                root.val = successor.val;
                root.right = DeleteNode(root.right, successor.val);
            }
        }
        
        return root;
    }
    
    private TreeNode FindMin(TreeNode node) {
        TreeNode current = node;
        while (current.left != null) {
            current = current.left;
        }
        return current;
    }
}

Time Complexity: O(h)

Where h is the height of the tree. In the worst case, O(n) for a skewed tree.

Space Complexity: O(h)

For the recursion stack.

Approach Explanation

The solution handles three cases for node deletion:

Key Insights:
- BST property maintenance
- Three deletion cases
- Successor finding
- Recursive approach
Algorithm Steps:
- Search for node
- Handle leaf nodes
- Handle single child
- Handle two children

Implementation Details:

Recursive search
Case handling
Successor finding
Tree restructuring

Optimization Insights:

Efficient search
Minimal restructuring
BST property usage
Memory management

Edge Cases:

Empty tree
Key not found
Root deletion
Single node