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:
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:
[0, 104].-105 <= Node.val <= 105root is a valid binary search tree.-105 <= key <= 105
Follow up: Could you solve it with time complexity O(height of tree)?
Problem Overview: You are given the root of a binary tree that follows the binary search tree property. The task is to delete a node with a given key and return the updated root while preserving BST ordering.
Approach 1: BST In-Place Deletion (O(h) time, O(h) space)
This method performs deletion directly inside the BST using recursive traversal. You first search for the target key using the BST property: move left if the key is smaller, right if larger. Once the node is found, handle three structural cases. If the node is a leaf, simply remove it. If it has one child, replace the node with that child. If it has two children, replace the node's value with its in-order successor (the smallest node in the right subtree) and delete that successor node. The recursion depth equals the tree height h, so time complexity is O(h) and space complexity is O(h) due to the call stack.
The key insight is that replacing the node with its in-order successor preserves the BST ordering constraint. The successor is guaranteed to be the next valid value in sorted order. After copying its value, deleting the successor becomes a simpler case because the successor cannot have a left child.
Approach 2: Iterative Deletion with Stack (O(h) time, O(h) space)
This version performs the same BST deletion logic but avoids recursion by explicitly tracking parent nodes using a stack or pointer references. You iterate through the tree to locate the node and keep track of its parent. After locating the node, apply the same three cases: leaf removal, single-child replacement, or successor substitution for two-child nodes. When the node has two children, find the in-order successor by moving to the right child and repeatedly following left pointers.
Iterative deletion is useful when recursion depth might be large or when you want tighter control over stack usage. The algorithm still runs in O(h) time because you only traverse the height of the BST to locate the node and possibly its successor. The auxiliary stack or parent tracking requires up to O(h) space.
Recommended for interviews: The recursive in-place BST deletion is the version most interviewers expect. It demonstrates that you understand BST structure and the three deletion cases. Showing the successor replacement logic clearly signals strong tree fundamentals. The iterative version is useful for follow-up discussions about recursion removal and memory control.
This approach involves traversing the tree recursively to find the node to be deleted. Once found, we handle it based on different cases: the node has no children, one child, or two children. For the two children case, replace the node with its inorder successor (minimum of the right subtree).
The function deleteNode recursively searches for the node with the provided key. If found, the node is deleted based on the number of its children. If the node has two children, it is replaced with its inorder successor.
Time Complexity: O(h), where h is the height of the tree.
Space Complexity: O(h) due to recursion stack space.
This method uses an iterative approach with a stack to traverse and manipulate the binary search tree. By applying the concept of replacing with the inorder successor, this method ensures the tree's properties remain intact after deletion.
This iterative solution modifies pointers directly, allowing for efficient deletion by using a double pointer strategy for parent-child relationships.
Time Complexity: O(h), where h is tree height.
Space Complexity: O(1) since no additional data structures are used.
| Approach | Complexity |
|---|---|
| BST In-Place Deletion | Time Complexity: O(h), where h is the height of the tree. |
| Iterative Deletion with Stack | Time Complexity: O(h), where h is tree height. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BST In-Place Deletion (Recursive) | O(h) | O(h) | Standard interview solution for BST deletion |
| Iterative Deletion with Stack | O(h) | O(h) | When avoiding recursion or controlling stack depth |
Delete Node in a BST - Leetcode 450 - Python • NeetCodeIO • 88,419 views views
Watch 9 more video solutions →Practice Delete Node in a BST with our built-in code editor and test cases.
Practice on FleetCode