How do you solve Delete Node in a BST?

Use a recursive DFS approach. At each node, compare the key with the node's value to decide whether to recurse left or right. Upon finding the node to delete, handle three cases: no children (return None), one child (return that child), or two children (replace with in-order successor and delete successor recursively). This guarantees O(h) time complexity, where h is the tree height.

What pattern does Delete Node in a BST use?

The Pattern: DFS (Recursive State Exploration in BST) The Heuristic: When modifying a BST, use recursion to navigate and update subtrees, handling deletion by carefully replacing nodes with their in-order successor or predecessor to maintain BST invariants.

Delete Node in a BST | DFS

Q: What is the time complexity of Delete Node in a BST?

O(h). The algorithm traverses from the root down to the node to delete, which takes O(h) time, where h is the height of the BST. Finding the in-order successor and deleting it also takes O(h) in the worst case.

Problem

Given the root of a binary search tree and a key, delete the node with the given key in the BST and return the root of the modified tree. You may assume the BST property must be maintained after deletion.

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⁵

Example

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

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

The node with value 3 is found. It has two children, so it is replaced by its in-order successor, which is 4. The successor node is then deleted from its original position. The resulting tree maintains the BST property.

Approach

Straightforward Solution

A brute-force approach might search for the node, then restructure the tree without careful handling of the BST property, potentially breaking the tree. Alternatively, one might try to rebuild the tree from scratch after deletion, which is inefficient.

Core Observation

In a BST, the left subtree contains values less than the node, and the right subtree contains values greater. Deleting a node requires preserving this property. When deleting a node with two children, replacing it with its in-order successor (the smallest node in the right subtree) maintains the BST structure.

Path to Optimal

Preview

The key insight is to use recursion to locate the node to delete. If the node has zero or one child, deletion is straightforward by returning the child or None…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a recursive DFS approach. At each node, compare the key with the node's value to decide whether to recurse left or right…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(h)

The algorithm traverses from the root down to the node to delete, which takes O(h) time, where h is the height of the BST. Finding the in-order successor and deleting it also takes O(h) in the worst case.

Space

O(h)

The recursion stack consumes O(h) space due to the depth of the tree. No additional data structures are used.

Solution

Python

1class Solution:
2    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
3        if not root:
4            return None
5
6        if key < root.val:
7            root.left = self.deleteNode(root.left, key)
8
9        elif key > root.val:
10            root.right = self.deleteNode(root.right, key)
11
12        else:
13            if not root.left:
14                return root.right
15
16            if not root.right:
17                return root.left
18
19            successor = root.right
20
21            while successor.left:
22                successor = successor.left
23
24            root.val = successor.val
25            root.right = self.deleteNode(root.right, successor.val)
26
27        return root

Step-by-Step Solution

1

Recursively Locate the Node to Delete

3if not root:
4    return None
6if key < root.val:
7    root.left = self.deleteNode(root.left, key)
9elif key > root.val:
10    root.right = self.deleteNode(root.right, key)

Objective

To traverse the BST recursively to find the node with the given key, directing the search left or right based on BST ordering.

Key Insight

The BST property allows pruning the search space: if the key is less than the current node's value, the node must be in the left subtree; if greater, in the right subtree. This reduces the search from O(n) to O(h), where h is the tree height. Recursion naturally handles subtree updates by returning the modified subtree root.

Interview Quick-Check

Core Logic

Use BST ordering to decide whether to recurse left or right, ensuring efficient search for the node to delete.

State & Boundaries

Return None immediately if the current node is None, indicating the key is not found in this path.

Common Pitfalls & Bugs

Failing to assign the recursive call's result back to root.left or root.right can cause the tree structure to remain unchanged after deletion.

2

Handle Deletion of Node with Zero or One Child

To delete the node when it has at most one child by returning the non-null child or None, effectively removing the node.

3

Replace Node with In-Order Successor and Delete Successor

To replace the node's value with its in-order successor's value and recursively delete the successor node from the right subtree.

4

Return the Updated Root After Deletion

To return the root of the updated subtree after deletion, allowing recursive calls to reconstruct the BST correctly.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 8 Critical lines interviewers watch for.

Line 12 Critical

else:

Identify the node to delete (key equals current node's value).

This condition triggers the deletion logic, distinguishing the node to remove from other nodes.

Line 21 Critical

while successor.left:

Traverse left to find the in-order successor (smallest node in right subtree).

Moving left until no further left child ensures the successor is the smallest node greater than the current node, preserving BST ordering.

Line 25 Critical

root.right = self.deleteNode(root.right, successor.val)

Recursively delete the successor node from the right subtree.

Deleting the successor node removes the duplicate and maintains BST integrity, completing the replacement process.

Full line-by-line criticality + rationale for all 17 lines available on Pro.

Test Your Understanding

Why is the in-order successor used to replace a node with two children during deletion in a BST?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Delete Node in a BST from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Delete Node in a BST drill

or drill a free problem

1	`class Solution:`
2	`def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:`
3	`if not root:`
4	`return None`
5
6	`if key < root.val:`
7	`root.left = self.deleteNode(root.left, key)`
8
9	`elif key > root.val:`
10	`root.right = self.deleteNode(root.right, key)`
11
12	`else:`
13	`if not root.left:`
14	`return root.right`
15
16	`if not root.right:`
17	`return root.left`
18
19	`successor = root.right`
20
21	`while successor.left:`
22	`successor = successor.left`
23
24	`root.val = successor.val`
25	`root.right = self.deleteNode(root.right, successor.val)`
26
27	`return root`

3	`if not root:`
4	`return None`
6	`if key < root.val:`
7	`root.left = self.deleteNode(root.left, key)`
9	`elif key > root.val:`
10	`root.right = self.deleteNode(root.right, key)`