Delete Node in a BST
The key idea
Deletion is a binary-search descent to locate the key, then a fix-up based on the node's children. A node with zero or one child is spliced out by returning its single child (or null). A node with two children cannot just vanish, so copy its in-order successor (the smallest value in the right subtree) into it, then recursively delete that successor from the right subtree, where it now has at most one child.
Problem
Given a reference to the root node of a binary search tree and an integer key, delete the node whose value equals key, if such a node exists, and return the reference to the (possibly updated) root of the tree.
Deletion proceeds in two stages: first search the tree for the node to remove, and if it is found, remove it while preserving the binary-search-tree property of the remaining nodes.
The returned tree need not be unique; any valid binary search tree that results from a correct deletion is accepted.
Constraints
- The number of nodes in the tree is in the range [0, 10^4].
- -10^5 <= Node.val <= 10^5
- Each node has a unique value.
- root is a valid binary search tree.
- -10^5 <= key <= 10^5
Examples
Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Input: root = [], key = 0
Output: []
Complexity
Time: O(h) Space: O(h)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY