Watch 10 video solutions for Delete Node in a BST, a medium level problem involving Tree, Binary Search Tree, Binary Tree. This walkthrough by NeetCodeIO has 88,419 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |