Delete Node in a BST - Solution & Explanation
Problem Statement
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, 104]. -105 <= Node.val <= 105- Each node has a unique value.
rootis a valid binary search tree.-105 <= key <= 105
Follow up: Could you solve it with time complexity O(height of tree)?
Approach Overview
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.
Approach 1: BST In-Place Deletion
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.
Complexity
Time Complexity: O(h), where h is the height of the tree.
Space Complexity: O(h) due to recursion stack space.
Approach 2: Iterative Deletion with Stack
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.
Complexity
Time Complexity: O(h), where h is tree height.
Space Complexity: O(1) since no additional data structures are used.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| 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. |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Delete Node in a BST - Leetcode 450 - Python • NeetCodeIO • 93,830 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Delete Node in a BST easy or hard?
Delete Node in a BST Python/Java solution
How to solve Delete Node in a BST in O(n)?
What is the best approach for Delete Node in a BST?
Is Delete Node in a BST asked at Google/Amazon/Meta?
What data structure is used in Delete Node in a BST?
What is the time complexity of Delete Node in a BST?
Ready to solve this problem?
Practice Delete Node in a BST with our built-in code editor and test cases.
Practice on FleetCode