-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDeleteNodeInaBST_450.java
More file actions
173 lines (157 loc) · 5.3 KB
/
Copy pathDeleteNodeInaBST_450.java
File metadata and controls
173 lines (157 loc) · 5.3 KB
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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
package com.leetcode.tree;
/**
* Created by charles on 1/2/17.
* 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:
Search for a node to remove.
If the node is found, delete the node.
root = [5,3,6,2,4,null,7]
key = 3
5
/ \
3 6
/ \ \
2 4 7
Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the following BST.
5
/ \
4 6
/ \
2 7
Another valid answer is [5,2,6,null,4,null,7].
5
/ \
2 6
\ \
4 7
*/
public class DeleteNodeInaBST_450 {
/**
* Recursively find the node that has the same value as the key, while setting the left/right nodes equal to the returned subtree
Once the node is found, have to handle the below 4 cases
node doesn't have left or right - return null
node only has left subtree- return the left subtree
node only has right subtree- return the right subtree
node has both left and right - find the minimum value in the right subtree, set that value to the currently found node, then recursively delete the minimum value in the right subtree
*/
public TreeNode deleteNodeRecursion(TreeNode root, int key) {
if (root == null) {
return null;
}
if (key < root.val) {
root.left = deleteNodeRecursion(root.left, key);
} else if (key > root.val) {
root.right = deleteNodeRecursion(root.right, key);
} else {
if (root.left == null) { // only has left subtree
return root.right;
} else if (root.right == null) { // only has right subtree
return root.left;
}
// has both left and right
// find minimum value of node in right subtree, then recursively remove that node
TreeNode leftMostInRightTree = findLeftMost(root.right);
root.val = leftMostInRightTree.val;
root.right = deleteNodeRecursion(root.right, root.val);
}
return root;
}
/**
* without recursion.
*/
public TreeNode deleteNodeI(TreeNode root, int key) {
if (root == null || root.val == key) {
return deleteRoot(root);
}
TreeNode node = root;
while (true) {
if (key > node.val) {
if (node.right == null || node.right.val == key) {
node.right = deleteRoot(node.right);
break;
}
node = node.right;
} else {
if (node.left == null || node.left.val == key) {
node.left = deleteRoot(node.left);
break;
}
node = node.left;
}
}
return root;
}
public TreeNode deleteNodeII(TreeNode root, int key) {
TreeNode curr = root;
TreeNode prev = null;
while (curr != null && curr.val != key) {
prev = curr;
if (key < curr.val) {
curr = curr.left;
} else if (key > curr.val) {
curr = curr.right;
}
}
TreeNode next = deleteSingleNode(curr);
if (prev == null) {
return next;
}
if (prev.left == curr) {
prev.left = next;
} else {
prev.right = next;
}
return root;
}
/** delete given root node */
public TreeNode deleteRoot(TreeNode root) {
if (root == null) {
return null;
}
if (root.right == null) {
return root.left;
}
// to give reference of root.right, instead pass as param directly
// TreeNode leftMostInRight = findLeftMost(root.right);
TreeNode rightTree = root.right;
TreeNode leftMostInRight = findLeftMost(rightTree);
// re-wire tree structure after remove original root.
leftMostInRight.left = root.left;
return root.right;
}
/** delete given input node from tree, return valid next node in tree */
public TreeNode deleteSingleNode(TreeNode node) {
if (node == null) { // case 1
return null;
}
if (node.left == null) { // case 2
return node.right;
}
if (node.right == null) { // case 3
return node.left;
}
// case 4;
TreeNode leftMostInRight = findLeftMost(node.right);
leftMostInRight.left = node.left;
return node.right;
}
/** from given node as root, find left most */
public TreeNode findLeftMost(TreeNode node) {
if (node == null) {
return null;
}
while (node.left != null) {
node = node.left;
}
return node;
}
public static void main(String[] args) {
TreeNode root = TreeNodeUtil.deserialize("5,3,6,2,4,#,7");
DeleteNodeInaBST_450 d = new DeleteNodeInaBST_450();
System.out.println(TreeNodeUtil.serialize(d.deleteNodeI(root, 3)));
System.out.println(TreeNodeUtil.serialize(d.deleteNodeRecursion(root, 3)));
System.out.println(TreeNodeUtil.serialize(d.deleteNodeII(root, 3)));
}
}