-
Notifications
You must be signed in to change notification settings - Fork 15
/
remove-node-in-binary-search-tree.java
125 lines (113 loc) · 4 KB
/
remove-node-in-binary-search-tree.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: The root of the binary search tree.
* @param value: Remove the node with given value.
* @return: The root of the binary search tree after removal.
*/
public TreeNode removeNode(TreeNode root, int value) {
// write your code here
// the idea is that: first search for the target node, then check
// its children, if no children then just remove current node, we also
// have to keep pareant node.
// If only one node, swap the value with child and remove child.
// If two children, swap value with predecessor and call remove method
// on predecessor.
if (root == null) {
return root;
}
// solution line number - 5: actual line number.
// TreeNode a = null;
// TreeNode b = a.left;
TreeNode runner = root;
TreeNode parent = null;
while (runner != null && runner.val != value) {
parent = runner;
if (runner.val < value) {
runner = runner.right;
} else {
runner = runner.left;
}
}
if (runner == null) {
// cannot find the target
return root;
}
// runner now is the target node.
// parent node is runner's parent.
if (runner.left == null && runner.right == null) {
if (parent == null) {
// removing root.
return null;
}
if (parent.left == runner) {
parent.left = null;
} else {
parent.right = null;
}
} else if (runner.left == null || runner.right == null) {
if (parent == null) {
// removing root that has one subtree
root = runner.left == null? runner.right : runner.left;
} else if (parent.left == runner) {
parent.left = runner.left == null? runner.right : runner.left;
} else {
parent.right = runner.left == null? runner.right : runner.left;
}
} else {
// has two children.
TreeNode pre = runner.left;
TreeNode preParent = null;
while (pre.right != null) {
preParent = pre;
pre = pre.right;
}
// if preParent is null, parent is runner.
runner.val = pre.val;
// Key observation here: predecessor can either has no children
// or at most has only left child.
if (pre.left == null) {
if (preParent == null) {
runner.left = null;
} else {
preParent.right = null;
}
} else {
// predecessor has left substree.
if (preParent == null) {
runner.left = pre.left;
} else {
preParent.right = pre.left;
}
}
// #####or:
// // key observation here: predecessor could have no children
// // or only one left subtree.
// if (pre.left == null) {
// // remove the pre.
// if (preParent.left == pre) {
// preParent.left = null;
// } else {
// preParent.right = null;
// }
// } else {
// if (preParent.left == pre) {
// preParent.left = pre.left;
// } else {
// preParent.right = pre.left;
// }
// }
}
return root;
}
}