Remove a Key From a Search Tree
Solve this ProblemYou are given the root of a binary search tree with distinct values and a key. Remove the node holding the key (if there is one) so that the tree remains a valid binary search tree, and return the root of the result. Use this rule for the shape: a leaf is deleted; a node with one child is replaced by that child; a node with two children takes over the value of its inorder successor (the smallest value in its right subtree) and the successor node is deleted instead.
The removal can be written recursively, or iteratively by remembering the parent of the node being unlinked.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100; all node values are distinct, 0 ≤ node.val ≤ 1000 - ◆
The tree is a binary search tree (left subtree smaller, right subtree larger at every node), given by its root node - ◆
key is any value between 0 and 1000; if it is not in the tree, nothing changes - ◆
Remove the node holding key so the tree stays a valid binary search tree, using this rule: a leaf is simply removed; a node with one child is replaced by that child; a node with two children takes over the value of its inorder successor (the smallest value in its right subtree), and that successor node is then removed instead. Return the root of the resulting tree (checked as a level-order list)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Recursive Removal That Returns the Fixed Subtree
GoodRecurse down the search path: a smaller key is removed from the left subtree and a larger key from the right one, and each call returns the (possibly new) root of its subtree so the parent can re-attach it. When the node is found: with no left child return its right child; with no right child return its left child; with two children find the inorder successor (go right once, then left as far as possible), copy its value into this node, and remove that value from the right subtree. It is short and clear, but keeps O(h) of call stack.
O(h)O(h)1class Solution {
2 public TreeNode removeKey(TreeNode root, int key) {
3 if (root == null) return null;
4 if (key < root.val) {
5 root.left = removeKey(root.left, key);
6 } else if (key > root.val) {
7 root.right = removeKey(root.right, key);
8 } else {
9 if (root.left == null) return root.right;
10 if (root.right == null) return root.left;
11 TreeNode succ = root.right;
12 while (succ.left != null) succ = succ.left;
13 root.val = succ.val;
14 root.right = removeKey(root.right, succ.val);
15 }
16 return root;
17 }
18}Optimal — Iterative With a Parent Pointer, O(1) Extra Space
OptimalDo the same thing with loops. First walk down while remembering the parent of the current node; if the key is missing, return the tree unchanged. If the node has two children, walk to its inorder successor while remembering the successor's parent, copy the successor's value into the node, and then treat the successor (which has no left child) as the node to unlink. Finally the node to unlink has at most one child: point its parent at that child (or, when it is the root, the child becomes the new root). No recursion, so O(1) extra space and O(h) time.
O(h)O(1)1class Solution {
2 public TreeNode removeKey(TreeNode root, int key) {
3 TreeNode parent = null, cur = root;
4 while (cur != null && cur.val != key) {
5 parent = cur;
6 cur = key < cur.val ? cur.left : cur.right;
7 }
8 if (cur == null) return root;
9 if (cur.left != null && cur.right != null) {
10 TreeNode succParent = cur, succ = cur.right;
11 while (succ.left != null) {
12 succParent = succ;
13 succ = succ.left;
14 }
15 cur.val = succ.val;
16 parent = succParent;
17 cur = succ;
18 }
19 TreeNode child = cur.left != null ? cur.left : cur.right;
20 if (parent == null) return child;
21 if (parent.left == cur) parent.left = child;
22 else parent.right = child;
23 return root;
24 }
25}