LeetCode 450 - Delete Node in a BST

Difficulty: 🟡 Medium
Topics: Tree, Binary Search Tree, Binary Tree

Solution

Problem Understanding

The problem asks us to delete a node with a specific value, key, from a Binary Search Tree, abbreviated as BST, and return the possibly updated root of the tree.

A Binary Search Tree has an important ordering property:

Every node in the left subtree contains a value smaller than the current node.
Every node in the right subtree contains a value larger than the current node.

Because all node values are unique, there is never ambiguity about where a value belongs.

The input consists of:

root, the root node of the BST
key, the value we want to remove from the tree

The output should be the root node of the updated BST after deletion. In some cases, the root itself may be deleted, so the returned root can be different from the original one.

The main challenge is preserving the BST property after deletion. Removing a node from a normal binary tree is simple, but in a BST we must carefully reconnect the remaining nodes so that the ordering remains valid.

There are three major deletion scenarios:

The node does not exist in the tree.
The node has zero or one child.
The node has two children.

The third case is the most important because simply removing the node would disconnect an entire subtree or violate BST ordering.

The constraints tell us that the tree can contain up to 10^4 nodes, which is large enough that inefficient rebuilding approaches become undesirable. The follow-up specifically asks for O(height of tree) complexity, which strongly hints that we should take advantage of BST ordering instead of traversing the entire tree unnecessarily.

Several edge cases are important:

The tree may be empty.
The key may not exist.
The node to delete may be the root.
The node may have no children.
The node may have only one child.
The node may have two children.
The BST may be highly unbalanced, effectively behaving like a linked list.

A correct implementation must handle all of these safely while maintaining BST structure.

Approaches

Brute Force Approach

A brute-force solution would ignore most of the BST structure. One possible strategy is:

Traverse the entire tree and collect all node values except the one being deleted.
Rebuild a new BST by inserting all remaining values one by one.

This approach works because inserting values into a BST reconstructs a valid BST structure. If the deleted key exists, it is simply omitted from reconstruction.

However, this method is inefficient for several reasons:

We traverse the whole tree even if the key is near the root.
We allocate extra memory to store all values.
Rebuilding the BST requires repeated insertions.
In the worst case, rebuilding can degrade to O(n^2).

The brute-force method ignores the key advantage of a BST, which is efficient search and modification based on ordering.

Optimal BST Deletion Approach

The better solution uses the BST property directly.

Since smaller values are always on the left and larger values are always on the right, we can locate the target node in O(height) time.

Once the node is found, deletion depends on the node's structure:

If the node has no children, remove it directly.
If the node has one child, replace the node with its child.
If the node has two children, replace its value with the inorder successor, then delete the successor node.

The inorder successor is the smallest node in the right subtree. Using it guarantees that BST ordering remains valid because:

Every node in the left subtree is still smaller.
Every node in the right subtree is still larger.

This allows us to delete nodes while preserving BST invariants efficiently.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²) worst case	O(n)	Traverse tree, store values, rebuild BST
Optimal	O(h)	O(h) recursive stack	Uses BST ordering for efficient deletion

Here, h represents the height of the tree.

Algorithm Walkthrough

Start at the root node and compare key with the current node's value.

If key is smaller, move to the left subtree because BST ordering guarantees the target can only exist there.

If key is larger, move to the right subtree for the same reason. 2. Continue recursively until either:

The node is found.
A None node is reached, meaning the key does not exist.

Once the target node is found, examine its children.

If the node has no left child, return its right child.

This effectively removes the node and reconnects the parent directly to the right subtree. 4. If the node has no right child, return its left child.

This mirrors the previous case. 5. If the node has both left and right children, find the inorder successor.

The inorder successor is the smallest node in the right subtree, which is found by repeatedly moving left. 6. Copy the inorder successor's value into the current node.

We do not physically move the successor node yet. Instead, we overwrite the current node's value. 7. Recursively delete the inorder successor from the right subtree.

Since the successor is the smallest node in the right subtree, it can never have a left child, making its deletion simpler. 8. Return the current node after all subtree updates are complete.

Why it works

The algorithm maintains the BST invariant at every step.

When traversing, BST ordering guarantees we only search one path from root to leaf.

When deleting:

Replacing a node with its single child preserves ordering because the subtree was already valid.
Using the inorder successor for two-child deletion preserves ordering because it is the next larger value in sorted order.

Thus, after deletion, every node still satisfies:

Left subtree values are smaller.
Right subtree values are larger.

Therefore, the resulting structure remains a valid BST.

Python Solution

# 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

from typing import Optional

class Solution:
    def deleteNode(
        self,
        root: Optional[TreeNode],
        key: int
    ) -> Optional[TreeNode]:

        if root is None:
            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 with only right child or no child
            if root.left is None:
                return root.right

            # Node with only left child
            if root.right is None:
                return root.left

            # Node with two children
            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:
        while node.left:
            node = node.left
        return node

The implementation begins with the recursive BST search logic. At each node, we compare key against root.val.

If the key is smaller, the algorithm recursively processes the left subtree. If larger, it processes the right subtree. This leverages BST ordering to avoid unnecessary traversal.

When the target node is found, the implementation handles deletion cases carefully.

If the node lacks a left child, the right child is returned directly. This reconnects the parent node with the remaining subtree.

If the node lacks a right child, the left child replaces it.

The most interesting case occurs when both children exist. The algorithm finds the inorder successor using findMin, which walks to the leftmost node in the right subtree.

The current node's value is replaced with the successor's value. Then the successor node itself is removed recursively from the right subtree.

Finally, each recursive call returns the updated subtree root, ensuring parent pointers remain correct throughout recursion.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil {
        return nil
    }

    if key < root.Val {
        root.Left = deleteNode(root.Left, key)
    } else if key > root.Val {
        root.Right = deleteNode(root.Right, key)
    } else {

        // No left child
        if root.Left == nil {
            return root.Right
        }

        // No right child
        if root.Right == nil {
            return root.Left
        }

        // Two children
        successor := findMin(root.Right)

        root.Val = successor.Val

        root.Right = deleteNode(root.Right, successor.Val)
    }

    return root
}

func findMin(node *TreeNode) *TreeNode {
    for node.Left != nil {
        node = node.Left
    }

    return node
}

The Go implementation closely mirrors the Python logic, but there are several language-specific differences.

Go uses nil instead of None for empty pointers. Tree nodes are manipulated using explicit pointers, so subtree updates occur through pointer reassignment.

Unlike Python, Go does not support nested helper methods inside functions naturally, so findMin is implemented as a separate function.

Integer overflow is not a concern here because node values remain within the problem constraints.

Worked Examples

Example 1

Input:

root = [5,3,6,2,4,null,7]
key = 3

Initial tree:

We want to delete node 3.

Step	Current Node	Action
1	5	3 < 5, move left
2	3	Node found
3	3	Node has two children
4	4	Find inorder successor
5	3 -> 4	Replace value
6	Delete 4	Remove successor node

Tree after replacement:

Output:

[5,4,6,2,null,null,7]

Example 2

Input:

root = [5,3,6,2,4,null,7]
key = 0

Step	Current Node	Action
1	5	0 < 5, move left
2	3	0 < 3, move left
3	2	0 < 2, move left
4	None	Key not found

No changes occur.

Output:

[5,3,6,2,4,null,7]

Example 3

Input:

root = []
key = 0

Step	Current Node	Action
1	None	Empty tree

Output:

[]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(h)	Only one root-to-leaf traversal is needed
Space	O(h)	Recursive call stack depth equals tree height

The algorithm traverses only a single path through the BST when searching for the node. Even when deleting a node with two children, finding the inorder successor also follows a single downward path.

Therefore, the total work is proportional to the tree height h.

In a balanced BST, height is O(log n). In the worst case, an unbalanced BST can degrade to height O(n).

The recursive implementation uses call stack space proportional to recursion depth, which is also O(h).

Test Cases

# Helper functions for testing

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

s = Solution()

# Test 1: Delete node with two children
root1 = TreeNode(
    5,
    TreeNode(3, TreeNode(2), TreeNode(4)),
    TreeNode(6, None, TreeNode(7))
)

result1 = s.deleteNode(root1, 3)
assert inorder(result1) == [2, 4, 5, 6, 7]  # delete internal node

# Test 2: Key does not exist
root2 = TreeNode(
    5,
    TreeNode(3, TreeNode(2), TreeNode(4)),
    TreeNode(6, None, TreeNode(7))
)

result2 = s.deleteNode(root2, 0)
assert inorder(result2) == [2, 3, 4, 5, 6, 7]  # unchanged tree

# Test 3: Empty tree
result3 = s.deleteNode(None, 0)
assert result3 is None  # empty input

# Test 4: Delete leaf node
root4 = TreeNode(2, TreeNode(1), TreeNode(3))

result4 = s.deleteNode(root4, 1)
assert inorder(result4) == [2, 3]  # leaf deletion

# Test 5: Delete root node
root5 = TreeNode(2, TreeNode(1), TreeNode(3))

result5 = s.deleteNode(root5, 2)
assert inorder(result5) == [1, 3]  # root deletion

# Test 6: Delete node with only left child
root6 = TreeNode(5, TreeNode(3, TreeNode(2)), None)

result6 = s.deleteNode(root6, 3)
assert inorder(result6) == [2, 5]  # one-child deletion

# Test 7: Delete node with only right child
root7 = TreeNode(5, None, TreeNode(7, None, TreeNode(8)))

result7 = s.deleteNode(root7, 7)
assert inorder(result7) == [5, 8]  # one-child deletion

# Test 8: Single-node tree
root8 = TreeNode(1)

result8 = s.deleteNode(root8, 1)
assert result8 is None  # tree becomes empty

# Test 9: Highly unbalanced tree
root9 = TreeNode(1)
root9.right = TreeNode(2)
root9.right.right = TreeNode(3)
root9.right.right.right = TreeNode(4)

result9 = s.deleteNode(root9, 3)
assert inorder(result9) == [1, 2, 4]  # linked-list shaped BST

Test	Why
Delete node with two children	Validates inorder successor logic
Key does not exist	Ensures tree remains unchanged
Empty tree	Confirms safe handling of null input
Delete leaf node	Tests simplest deletion case
Delete root node	Verifies root replacement logic
Delete node with only left child	Tests one-child reconnection
Delete node with only right child	Tests symmetric one-child case
Single-node tree	Ensures tree can become empty
Highly unbalanced tree	Tests worst-case BST structure

Edge Cases

Deleting the Root Node

Deleting the root is often a source of bugs because the tree's entry point may change. If the implementation only updates child pointers without returning the new subtree root, the caller may retain an outdated reference.

This implementation avoids the issue by always returning the updated root from recursive calls. If the root is deleted and replaced by one of its children, the caller receives the correct new root.

Deleting a Node With Two Children

This is the most complex scenario because removing the node directly would disconnect subtrees or violate BST ordering.

The implementation handles this by replacing the node's value with the inorder successor, which is guaranteed to be the next larger value in sorted order. The successor node is then deleted recursively from the right subtree.

Because the successor is the smallest node in the right subtree, BST ordering remains valid after replacement.

Key Does Not Exist

A naive implementation might accidentally modify the tree while searching unsuccessfully for the key.

This solution safely traverses the BST until it reaches None. At that point, recursion unwinds without changing any pointers, so the original tree structure remains intact.

Empty Tree

An empty tree is represented by root = None. Attempting to access child pointers or node values without checking for this condition would cause runtime errors.

The implementation immediately returns None when the root is empty, making the operation safe and efficient.