Delete Node in a BST solution and explanation
Infosys
Google
9 more videos on this problem
Delete Node in a BST - Leetcode 450 - PythonNeetCodeIO · 12:59 · 93K views
Leetcode - Delete Node in a BST (Python)Timothy H Chang · 8:30 · 16K views
[Java] Leetcode 450. Delete Node in a BST [Binary Search Tree #5]Eric Programming · 9:45 · 8K views
Delete Node in a BST - LeetCode 450 - Python #leetcode #leetcode75Deepti Talesra · 17:45 · 3K views
Delete A Node In BST | LeeCode August Challenge (Day31) | Leetcode 450Coding Decoded · 9:27 · 903 views
Delete Node in a BST [Leetcode 450, medium]Daily Dose of LeetCode · 7:50 · 255 views
Daily Leetcode #601: Nov 22, 2021 - 450. Delete Node in a BSTProgramming Live with Larry · 54:20 · 233 views
Delete Node in a BST | Leetcode 450 | Amazon Google Facebook interview questionSuper Lazy Coder · 14:03 · 206 views
Delete ANY Node in a Binary Search Tree LIKE A PRO LeetCode 450. Delete Node in a BST in PythonvanAmsen · 6:01 · 191 views
Delete Node in a BST - LeetCode 450 - PythonAlpha-Code · 17:07 · 167 views
The problem
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).
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def deleteNode(root: TreeNode, key: int) -> TreeNode:
if not root:
return None
if key < root.val:
root.left = deleteNode(root.left, key)
elif key > root.val:
root.right = deleteNode(root.right, key)
else:
if not root.left:
return root.right
if not root.right:
return root.left
minLargerNode = getMin(root.right)
root.val = minLargerNode.val
root.right = deleteNode(root.right, minLargerNode.val)
return root
def getMin(node):
while node.left:
node = node.left
return nodepublic TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return root;
if (key < root.val) {
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
root.right = deleteNode(root.right, key);
} else {
if (root.left == null) return root.right;
if (root.right == null) return root.left;
TreeNode minNode = getMin(root.right);
root.val = minNode.val;
root.right = deleteNode(root.right, minNode.val);
}
return root;
}
private TreeNode getMin(TreeNode node) {
while (node.left != null) node = node.left;
return node;
}TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return root;
if (key < root->val) {
root->left = deleteNode(root->left, key);
} else if (key > root->val) {
root->right = deleteNode(root->right, key);
} else {
if (!root->left) return root->right;
if (!root->right) return root->left;
TreeNode* minNode = getMin(root->right);
root->val = minNode->val;
root->right = deleteNode(root->right, minNode->val);
}
return root;
}
TreeNode* getMin(TreeNode* node) {
while (node->left) node = node->left;
return node;
}function deleteNode(root, key) {
if (root === null) return root;
if (key < root.val) {
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
root.right = deleteNode(root.right, key);
} else {
if (root.left === null) return root.right;
if (root.right === null) return root.left;
let minNode = getMin(root.right);
root.val = minNode.val;
root.right = deleteNode(root.right, minNode.val);
}
return root;
}
function getMin(node) {
while (node.left !== null) node = node.left;
return node;
}TreeNode* deleteNode(TreeNode* root, int key) {
if (root == NULL) return root;
if (key < root->val) {
root->left = deleteNode(root->left, key);
} else if (key > root->val) {
root->right = deleteNode(root->right, key);
} else {
if (root->left == NULL) {
TreeNode* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
TreeNode* temp = root->left;
free(root);
return temp;
}
TreeNode* temp = minValueNode(root->right);
root->val = temp->val;
root->right = deleteNode(root->right, temp->val);
}
return root;
}
TreeNode* minValueNode(TreeNode* node) {
TreeNode* current = node;
while (current && current->left != NULL) {
current = current->left;
}
return current;
}public TreeNode DeleteNode(TreeNode root, int key) {
if (root == null) return null;
if (key < root.val) {
root.left = DeleteNode(root.left, key);
} else if (key > root.val) {
root.right = DeleteNode(root.right, key);
} else {
if (root.left == null) return root.right;
if (root.right == null) return root.left;
TreeNode minNode = GetMin(root.right);
root.val = minNode.val;
root.right = DeleteNode(root.right, minNode.val);
}
return root;
}
private TreeNode GetMin(TreeNode node) {
while (node.left != null) node = node.left;
return node;
}This implementation of BST node deletion is recursive and handles various node configurations, replacing the target node with its inorder successor if it has two children.
Time Complexity: O(h), where h is the height of the tree.
Space Complexity: O(h) for the recursion stack.
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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def deleteNode(root, key):
dummy = TreeNode(0)
dummy.left = root
parent, node = dummy, root
while node and node.val != key:
parent = node
if key < node.val:
node = node.left
else:
node = node.right
if node:
if node.left and node.right:
minLargerNode, parent = node.right, node
while minLargerNode.left:
parent = minLargerNode
minLargerNode = minLargerNode.left
node.val = minLargerNode.val
node = minLargerNode
if node == parent.left:
parent.left = node.left if node.left else node.right
else:
parent.right = node.left if node.left else node.right
return dummy.leftpublic TreeNode deleteNode(TreeNode root, int key) {
TreeNode dummy = new TreeNode(0);
dummy.left = root;
TreeNode parent = dummy, node = root, p = parent;
while (node != null && node.val != key) {
p = parent;
parent = node;
node = key < node.val ? node.left : node.right;
}
if (node != null) {
deleteNode(node, parent, p);
}
return dummy.left;
}
private void deleteNode(TreeNode node, TreeNode parent, TreeNode p) {
if (node.left == null || node.right == null) {
TreeNode newChild = node.left != null ? node.left : node.right;
if (parent.left == node) parent.left = newChild;
else parent.right = newChild;
} else {
TreeNode minNode = node.right, minParent = node;
while (minNode.left != null) {
minParent = minNode;
minNode = minNode.left;
}
node.val = minNode.val;
deleteNode(minNode, minParent, minNode);
}
}TreeNode* deleteNode(TreeNode* root, int key) {
TreeNode** cur = &root, **back = nullptr;
while (*cur && (*cur)->val != key)
cur = key < (*cur)->val ? &(*cur)->left : &(*cur)->right;
if (*cur) removeNode(cur);
return root;
}
void removeNode(TreeNode** node) {
TreeNode* toDelete = *node;
if (!(*node)->left)
*node = (*node)->right;
else if (!(*node)->right)
*node = (*node)->left;
else {
TreeNode** successor = &(*node)->right;
while ((*successor)->left) successor = &(*successor)->left;
(*node)->val = (*successor)->val;
removeNode(successor);
}
delete toDelete;
}function deleteNode(root, key) {
const dummy = { left: root };
let parent = dummy, node = root;
while (node && node.val !== key) {
parent = node;
if (key < node.val) node = node.left;
else node = node.right;
}
if (node) {
if (node.left && node.right) {
let successor = node.right, successorParent = node;
while (successor.left) {
successorParent = successor;
successor = successor.left;
}
node.val = successor.val;
node = successor;
parent = successorParent;
}
const child = node.left ? node.left : node.right;
if (parent.left === node) parent.left = child;
else parent.right = child;
}
return dummy.left;
}TreeNode* deleteNode(TreeNode* root, int key) {
TreeNode** curr = &root, *temp;
while (*curr != NULL && (*curr)->val != key) {
curr = (key < (*curr)->val) ? &(*curr)->left : &(*curr)->right;
}
if (*curr == NULL) return root;
if ((*curr)->left == NULL) {
temp = *curr;
*curr = (*curr)->right;
free(temp);
} else if ((*curr)->right == NULL) {
temp = *curr;
*curr = (*curr)->left;
free(temp);
} else {
temp = (*curr)->right;
while (temp->left != NULL) temp = temp->left;
(*curr)->val = temp->val;
(*curr)->right = deleteNode((*curr)->right, temp->val);
}
return root;
}public TreeNode DeleteNode(TreeNode root, int key) {
TreeNode dummy = new TreeNode(0);
dummy.left = root;
TreeNode parent = dummy, node = root;
while (node != null && node.val != key) {
parent = node;
if (key < node.val) node = node.left;
else node = node.right;
}
if (node != null) {
if (node.left != null && node.right != null) {
TreeNode succ = node.right, succParent = node;
while (succ.left != null) {
succParent = succ;
succ = succ.left;
}
node.val = succ.val;
node = succ;
parent = succParent;
}
TreeNode child = node.left != null ? node.left : node.right;
if (parent.left == node) parent.left = child;
else parent.right = child;
}
return dummy.left;
}This iterative Python solution uses a dummy node to help bypass complications from root node deletion and ensures an effective, non-recursive approach.
Time Complexity: O(h), where h is the tree's height.
Space Complexity: O(1), as the approach is purely iterative.
Approach 3: Default Approach
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
if (root == null) {
return root;
}
const { val, left, right } = root;
if (val > key) {
root.left = deleteNode(left, key);
} else if (val < key) {
root.right = deleteNode(right, key);
} else {
if (left == null && right == null) {
root = null;
} else if (left == null || right == null) {
root = left || right;
} else {
if (right.left == null) {
right.left = left;
root = right;
} else {
let minPreNode = right;
while (minPreNode.left.left != null) {
minPreNode = minPreNode.left;
}
const minVal = minPreNode.left.val;
root.val = minVal;
minPreNode.left = deleteNode(minPreNode.left, minVal);
}
}
}
return root;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func deleteNode(root *TreeNode, key int) *TreeNode {
if root == nil {
return nil
}
if root.Val > key {
root.Left = deleteNode(root.Left, key)
return root
}
if root.Val < key {
root.Right = deleteNode(root.Right, key)
return root
}
if root.Left == nil {
return root.Right
}
if root.Right == nil {
return root.Left
}
node := root.Right
for node.Left != nil {
node = node.Left
}
node.Left = root.Left
root = root.Right
return root
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
fn dfs(root: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
let node = root.as_ref().unwrap().borrow();
if node.left.is_none() {
return node.val;
}
Self::dfs(&node.left)
}
pub fn delete_node(
mut root: Option<Rc<RefCell<TreeNode>>>,
key: i32,
) -> Option<Rc<RefCell<TreeNode>>> {
if root.is_some() {
let mut node = root.as_mut().unwrap().borrow_mut();
match node.val.cmp(&key) {
std::cmp::Ordering::Less => {
node.right = Self::delete_node(node.right.take(), key);
}
std::cmp::Ordering::Greater => {
node.left = Self::delete_node(node.left.take(), key);
}
std::cmp::Ordering::Equal => {
match (node.left.is_some(), node.right.is_some()) {
(false, false) => {
return None;
}
(true, false) => {
return node.left.take();
}
(false, true) => {
return node.right.take();
}
(true, true) => {
if node.right.as_ref().unwrap().borrow().left.is_none() {
let mut r = node.right.take();
r.as_mut().unwrap().borrow_mut().left = node.left.take();
return r;
} else {
let val = Self::dfs(&node.right);
node.val = val;
node.right = Self::delete_node(node.right.take(), val);
}
}
};
}
}
}
root
}
}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 the tree's height. |
| Default Approach | – |
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 |
Frequently asked questions
Is Delete Node in a BST easy or hard?
Delete Node in a BST is generally classified as a Medium difficulty problem. The challenge comes from correctly handling the three deletion scenarios and maintaining BST ordering while updating tree pointers.
Delete Node in a BST Python/Java solution
Python and Java implementations typically follow the same recursive strategy. Search for the key, handle the three deletion cases, and when two children exist replace the node value with the in-order successor from the right subtree before deleting that successor node.
How to solve Delete Node in a BST in O(n)?
A straightforward solution traverses the tree to locate the node and adjusts pointers during deletion. In the worst case where the BST becomes skewed like a linked list, the height becomes n, giving O(n) time complexity. Balanced BST structures typically reduce this to O(log n).
What is the best approach for Delete Node in a BST?
The best approach is in-place BST deletion using the in-order successor. Traverse the tree to find the node, then handle three cases: leaf node removal, single-child replacement, or replacing the node with its successor if it has two children. This keeps the BST ordering intact and runs in O(h) time where h is the tree height.
Is Delete Node in a BST asked at Google/Amazon/Meta?
Delete Node in a BST is a common tree interview problem and variations have appeared in interviews at companies like Google, Amazon, and Meta. Interviewers use it to test understanding of BST invariants, recursion, and handling multiple structural cases in tree manipulation.
What data structure is used in Delete Node in a BST?
The problem uses a Binary Search Tree data structure. BST properties allow efficient searching and deletion by ensuring that left subtree values are smaller and right subtree values are larger than the node value.
What is the time complexity of Delete Node in a BST?
Deletion in a Binary Search Tree takes O(h) time, where h is the height of the tree. In balanced BSTs this becomes O(log n), while in the worst case of a skewed tree it can degrade to O(n). Finding the node and locating the in-order successor both operate within the tree height.