Delete Node in a BST
Delete Node in a BST is LeetCode 450 (Medium). You are given the root of a binary search tree and a key. Remove the node holding key, if there is one, and return the root of the resulting tree, which must still be a valid BST.
- The tree may be empty, and
keymay not be in it. - All values are unique.
The tree holds up to 10⁴ nodes, and the follow-up asks for O(h) time, where h is the height of the tree.
- The number of nodes in the tree is in the range [0, 10⁴].
- -10⁵ <= Node.val <= 10⁵
- Each node has a unique value.
- root is a valid binary search tree.
- -10⁵ <= key <= 10⁵
Intuition
The BST order tells you where key must be, so finding it is a walk down one path. Removing it is the hard part, because its parent must still point to a valid subtree. What takes its place depends on how many children it has:
- No children: nothing takes its place; the parent points to nothing.
- One child: that child moves up. Everything under it is already on the correct side of the parent.
- Two children: copy in the in-order successor, the smallest value in the right subtree. It is larger than everything on the left and smaller than everything else on the right, so the order still holds. Then delete the successor's original node, which has no left child, so it is one of the easy cases.
Any recursive change that may replace a node has this shape: each call returns the new root of its subtree, and the parent stores what comes back. Insert into a BST, trim a BST and prune a tree use the same pattern.
Approach
Before reading on, picture a node with two children. Which value already in the tree could take its place so that every node stays in order? Then ask why removing that value's original node is easy. Aim for O(h).
Walk down to the key
If key < root.val, delete it from the left subtree and store the result in root.left; if larger, do the same on the right. Each call returns the root of its subtree after the deletion, so the parent always re-links to whatever comes back. An empty subtree means the key is absent: return None and nothing changes.
Zero or one child: return the other side
Once root.val == key:
- no left child: return
root.right; - no right child: return
root.left.
The parent stores the returned subtree, so the node drops out. A leaf takes the first branch and returns None.
Two children: find the successor
Start at root.right and keep going left until a node has no left child. That node holds the smallest value larger than key, the one value that fits between the left subtree and the rest of the right subtree.
Copy it, then delete the original
Write the successor's value into root, then call deleteNode(root.right, successor.val) and store the result in root.right. The successor has no left child, so this second call always ends in the zero-or-one-child case. Return root.
Delete Node in a BST solution in Python | C++ | Java
root.left.None. The parent stores it as its right child, so the node simply disappears; a leaf needs no case of its own.root.left.root.left.root.left.None hands the parent back exactly what it already had there, so nothing changes.Common pitfalls
Not assigning the recursive result back
self.deleteNode(root.left, key)
root.left = self.deleteNode(root.left, key)
The recursion returns the new subtree root, which may differ after a deletion. Discarding it leaves the parent pointing at the old subtree, so a deleted leaf or one-child node stays in the tree.
Taking the successor from the wrong side
successor = root.left while successor.left: ...
successor = root.right while successor.left: ...
The in-order successor is the smallest value in the right subtree, reached by going right once then left as far as possible. Descending left from the start finds an unrelated node and breaks the ordering.
Forgetting to delete the duplicated successor
root.val = successor.val return root
root.val = successor.val root.right = self.deleteNode(root.right, successor.val)
Copying the value leaves two nodes holding it, so the original successor must still be removed from the right subtree.
Edge cases
The top call returns whatever replaces it. Deleting 5 from [5,3,6,2,4,null,7] copies 6 into the root, so the answer is [6,3,7,2,4].
Removing the successor's original node returns its right child, which moves up into its place. In the example above, 7 moves up when the old 6 is removed.
Complexity
Delete Node in a BST FAQ
Can you delete a node without copying values?
Yes. Find the successor, remove it from the right subtree, then give it the deleted node's left and right children and return it in the node's place. It costs the same O(h) and is preferred when nodes carry other data. An iterative version that tracks the parent pointer also brings the extra space down to O(1).
Can you use the in-order predecessor instead of the successor?
Yes. The predecessor is the largest value in the left subtree: go left once, then right as far as possible. It also fits between the two subtrees, and its node has no right child, so deleting it is just as easy.
How is deletion in a binary search tree different from a plain binary tree?
A plain binary tree has no order, so finding the node takes a full O(n) search, and the usual fix is to overwrite it with the deepest rightmost node. In a BST the order guides the search down one path in O(h), and the replacement must be the successor or predecessor to keep that order.