450 Delete Node in a BST

1. Question

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:
  1. 1.
    Search for a node to remove.
  2. 2.
    If the node is found, delete the node.
Note:Time complexity should be O(height of tree).
Example:
1
root = [5,3,6,2,4,null,7]
2
key = 3
3
4
5
5
/ \
6
3 6
7
/ \ \
8
2 4 7
9
10
Given key to delete is 3. So we find the node with value 3 and delete it.
11
12
One valid answer is [5,4,6,2,null,null,7], shown in the following BST.
13
14
5
15
/ \
16
4 6
17
/ \
18
2 7
19
20
Another valid answer is [5,2,6,null,4,null,7].
21
22
5
23
/ \
24
2 6
25
\ \
26
4 7
Copied!

2. Implementation

(1) Iteration
1
class Solution {
2
public TreeNode deleteNode(TreeNode root, int key) {
3
TreeNode preNode = null, curNode = root;
4
5
while (curNode != null && curNode.val != key) {
6
preNode = curNode;
7
if (curNode.val < key) {
8
curNode = curNode.right;
9
}
10
else{
11
curNode = curNode.left;
12
}
13
}
14
15
if (preNode == null) {
16
return getSuccessor(curNode);
17
}
18
else if (preNode.left == curNode) {
19
preNode.left = getSuccessor(curNode);
20
}
21
else if (preNode.right == curNode) {
22
preNode.right = getSuccessor(curNode);
23
}
24
return root;
25
}
26
27
public TreeNode getSuccessor(TreeNode node) {
28
if (node == null) {
29
return null;
30
}
31
32
if (node.left == null) {
33
return node.right;
34
}
35
36
if (node.right == null) {
37
return node.left;
38
}
39
40
TreeNode preNode = null, successor = node.right;
41
42
while (successor.left != null) {
43
preNode = successor;
44
successor = successor.left;
45
}
46
47
successor.left = node.left;
48
if (node.right != successor) {
49
preNode.left = successor.right;
50
successor.right = node.right;
51
}
52
return successor;
53
}
54
}
Copied!
(2) Recursion
1
/**
2
* Definition for a binary tree node.
3
* public class TreeNode {
4
* int val;
5
* TreeNode left;
6
* TreeNode right;
7
* TreeNode(int x) { val = x; }
8
* }
9
*/
10
class Solution {
11
public TreeNode deleteNode(TreeNode root, int key) {
12
if (root == null) {
13
return null;
14
}
15
16
if (root.val < key) {
17
root.right = deleteNode(root.right, key);
18
}
19
else if (root.val > key) {
20
root.left = deleteNode(root.left, key);
21
}
22
else {
23
if (root.left == null) {
24
return root.right;
25
}
26
27
if (root.right == null) {
28
return root.left;
29
}
30
31
TreeNode successor = getInorderSuccessor(root.right);
32
// 注意这一步是改变了原来的数据,面试时不一定被允许
33
root.val = successor.val;
34
root.right = deleteNode(root.right, root.val);
35
}
36
return root;
37
}
38
39
public TreeNode getInorderSuccessor(TreeNode node) {
40
while (node.left != null) {
41
node = node.left;
42
}
43
return node;
44
}
45
}
Copied!

3. Time & Space Complexity

Iteration:时间复杂度O(h), 空间复杂度O(1)
Recursion: 时间复杂度O(h), 空间复杂度O(h)