Delete Node in a BST
Medium · Trees · Explanation and code example
Iteration
How it works
This approach avoids recursion by using a loop to find the node to delete and its parent. Once found, we handle the same three deletion cases, but we manually update parent pointers. When the node has two children, we find the in-order successor, detach it from its position, and replace the deleted node with it. This requires careful pointer manipulation to maintain tree structure.
Steps
- If the root is
null, returnnull. - Use a loop to find the node with the given key, tracking its parent.
- If the node is not found, return the original root.
- If the node has zero or one child:
- Determine the child (left or right, whichever exists).
- If deleting the root, return the child.
- Otherwise, update the parent's pointer to point to the child.
- If the node has two children:
- Find the in-order successor (leftmost node in the right subtree) and its parent.
- If the successor is not the immediate right child, update its parent's left pointer to the successor's right child, then set the successor's right to the deleted node's right.
- Set the successor's left to the deleted node's left.
- Update the parent's pointer to the successor, or return the successor if deleting the root.
- Return the root.
Complexity
- Time complexity:
O(h) - Space complexity:
O(1)extra space.
Where
his the height of the given binary search tree.
Things to watch for
Confusing In-Order Successor with In-Order Predecessor
When a node has two children, you can replace it with either the in-order successor (smallest in right subtree) or in-order predecessor (largest in left subtree). Mixing these up or searching in the wrong subtree leads to an invalid BST.
Forgetting to Handle the Case When Key Is Not Found
If the key does not exist in the BST, the function should return the tree unchanged. Failing to handle this case can lead to incorrect behavior or null pointer exceptions.
Not Returning the Modified Subtree in Recursive Calls
Each recursive call modifies a subtree and returns its new root. Forgetting to assign the return value back to root.left or root.right means the deletion is not reflected in the tree.
Python code example
from typing import Optional
# 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
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if not root:
return root
parent = None
cur = root
# Find the node to delete
while cur and cur.val != key:
parent = cur
if key > cur.val:
cur = cur.right
else:
cur = cur.left
if not cur:
return root
# Node with only one child or no child
if not cur.left or not cur.right:
child = cur.left if cur.left else cur.right
if not parent:
return child
if parent.left == cur:
parent.left = child
else:
parent.right = child
else:
# Node with two children
par = None # parent of right subTree min node
delNode = cur
cur = cur.right
while cur.left:
par = cur
cur = cur.left
if par: # if there was a left traversal
par.left = cur.right
cur.right = delNode.right
cur.left = delNode.left
if not parent: # if we're deleting root
return cur
if parent.left == delNode:
parent.left = cur
else:
parent.right = cur
return root
C++ code example
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return root;
TreeNode* parent = nullptr;
TreeNode* cur = root;
// Find the node to delete
while (cur && cur->val != key) {
parent = cur;
if (key > cur->val) {
cur = cur->right;
} else {
cur = cur->left;
}
}
if (!cur) return root;
// Node with only one child or no child
if (!cur->left || !cur->right) {
TreeNode* child = cur->left ? cur->left : cur->right;
if (!parent) return child;
if (parent->left == cur) {
parent->left = child;
} else {
parent->right = child;
}
} else {
// Node with two children
TreeNode* par = nullptr; // parent of right subtree's min node
TreeNode* delNode = cur;
cur = cur->right;
while (cur->left) {
par = cur;
cur = cur->left;
}
if (par) { // if there was a left traversal
par->left = cur->right;
cur->right = delNode->right;
}
cur->left = delNode->left;
if (!parent) return cur; // if deleting root
if (parent->left == delNode) {
parent->left = cur;
} else {
parent->right = cur;
}
}
return root;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.