LeetCode Solutions Blog

Delete Node in a BST

Number: 450

Difficulty: Medium

Paid? No

Problem Description

Given the root node of a Binary Search Tree (BST) and a key, delete the node with the given key and return the (possibly updated) root of the BST. The deletion is performed in two stages: first, search for the node; second, delete it while maintaining the BST properties.

Key Insights

If the key is not found in the BST, return the original tree.
There are three deletion cases:
- The node is a leaf (no children).
- The node has one child (left or right).
- The node has two children.
For a node with two children, find the inorder successor (smallest node in the right subtree) or the inorder predecessor (largest node in the left subtree) to replace the node's value.
Recursively adjust the tree to preserve the BST invariants.

Space and Time Complexity

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), due to the recursion stack.

Solution

We use a recursive approach to traverse the tree to find the node with the given key. When the node is found:

If it has zero or one child, return the non-null child or null.
If it has two children, find the inorder successor (the smallest node in the right subtree), copy its value to the current node, and then delete the successor recursively. This ensures that the BST property is maintained after deletion.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val           # Node's value
        self.left = left         # Pointer to left child
        self.right = right       # Pointer to right child

class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        if not root:
            # If the tree is empty, return None.
            return None
        if key < root.val:
            # If the key is less, go to the left subtree.
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:
            # If the key is greater, go to the right subtree.
            root.right = self.deleteNode(root.right, key)
        else:
            # Key found; now perform deletion.
            if not root.left:
                # Node with only right child or no child.
                return root.right
            elif not root.right:
                # Node with only left child.
                return root.left
            else:
                # Node has two children.
                # Find the inorder successor (smallest in the right subtree).
                temp = root.right
                while temp.left:
                    temp = temp.left
                # Replace the value of the node to be deleted.
                root.val = temp.val
                # Delete the inorder successor.
                root.right = self.deleteNode(root.right, temp.val)
        return root