master
1<<-DOC
2A tree is considered a binary search tree (BST) if for each of its nodes the following is true:
3
4The left subtree of a node contains only nodes with keys less than the node's key.
5The right subtree of a node contains only nodes with keys greater than the node's key.
6Both the left and the right subtrees must also be binary search trees.
7Removing a value x from a BST t is done in the following way:
8
9If there is no x in t, nothing happens;
10Otherwise, let t' be a subtree of t such that t'.value = x.
11If t' has a left subtree, remove the rightmost node from it and put it at the root of t';
12Otherwise, remove the root of t' and its right subtree becomes the new t's root.
13For example, removing 4 from the following tree has no effect because there is no such value in the tree:
14
15 5
16 / \
17 2 6
18 / \ \
191 3 8
20 /
21 7
22Removing 5 causes 3 (the rightmost node in left subtree) to move to the root:
23
24 3
25 / \
26 2 6
27 / \
281 8
29 /
30 7
31And removing 6 after that creates the following tree:
32
33 3
34 / \
35 2 8
36 / /
371 7
38You're given a binary search tree t and an array of numbers queries. Your task is to remove queries[0], queries[1],
39etc., from t, step by step, following the algorithm above. Return the resulting BST.
40
41Example
42
43For
44
45t = {
46 "value": 5,
47 "left": {
48 "value": 2,
49 "left": {
50 "value": 1,
51 "left": null,
52 "right": null
53 },
54 "right": {
55 "value": 3,
56 "left": null,
57 "right": null
58 }
59 },
60 "right": {
61 "value": 6,
62 "left": null,
63 "right": {
64 "value": 8,
65 "left": {
66 "value": 7,
67 "left": null,
68 "right": null
69 },
70 "right": null
71 }
72 }
73}
74and queries = [4, 5, 6], the output should be
75
76deleteFromBST(t, queries) = {
77 "value": 3,
78 "left": {
79 "value": 2,
80 "left": {
81 "value": 1,
82 "left": null,
83 "right": null
84 },
85 "right": null
86 },
87 "right": {
88 "value": 8,
89 "left": {
90 "value": 7,
91 "left": null,
92 "right": null
93 },
94 "right": null
95 }
96}
97Input/Output
98
99[time limit] 4000ms (rb)
100[input] tree.integer t
101
102A tree of integers.
103
104Guaranteed constraints:
1050 ≤ t size ≤ 1000,
106-109 ≤ node value ≤ 109.
107
108[input] array.integer queries
109
110An array that contains the numbers to be deleted from t.
111
112Guaranteed constraints:
1131 ≤ queries.length ≤ 1000,
114-109 ≤ queries[i] ≤ 109.
115
116[output] tree.integer
117
118The tree after removing all the numbers in queries, following the algorithm above.
119DOC
120
121describe "#delete_from_bst" do
122 <<-DOC
123 If there is no x in t, nothing happens;
124 Otherwise, let t' be a subtree of t such that t'.value = x.
125 If t' has a left subtree, remove the rightmost node from it and put it at the root of t';
126 Otherwise, remove the root of t' and its right subtree becomes the new t's root.
127
128 If t' has a left subtree and the left subtree has a child on the right,
129 the node you should put at the root of t' is the rightmost node (not necessarily leaf) in this subtree.
130 When you remove the rightmost node, you must also discard its children
131 (rather than keeping them as children of the rightmost node's parent).
132
133 3
134 / \
135 2 5
136 /
1371
138remove 3:
139
140 2
141 / \
1421 5
143
144remove 2:
145
146 1
147 \
148 5
149
150remove 1
151
152 5
153
154
155
156And removing 6 after that creates the following tree:
157
158{ value: 3, left: { value: 2, left: { value: 1 } }, right: { value: 6, left: { value: 5 }, right: { value: 8, left: { value: 7 } } } }
159 3
160 / \
161 2 6
162 / / \
1631 5 8
164 /
165 7
166
167{ value: 3, left: { value: 2, left: { value: 1 } }, right: { value: 5, right: { value: 8, left: { value: 7 } } } }
168 3
169 / \
170 2 5
171 / \
1721 8
173 /
174 7
175
176
177Instead of recursively removing the largest node from the right subtree using the specified algorithm,
178they want you to take the largest node's left subtree and make it the child of the largest node's parent
179 DOC
180
181 def remove(tree, target)
182 return nil if tree.nil?
183
184 if target < tree.value
185 tree.left = remove(tree.left, target)
186 elsif tree.value < target
187 tree.right = remove(tree.right, target)
188 else
189 if tree.left.nil?
190 return tree.right
191 elsif tree.right.nil?
192 return tree.left
193 else
194 max, parent = tree.left, tree
195 while max.right
196 parent = max
197 max = max.right
198 end
199
200 tree.value = max.value
201 if parent == tree
202 tree.left = tree.left.left
203 else
204 parent&.right = max.left
205 end
206
207 #max = tree.left
208 #max = max.right while max.right
209 #tree.value = max.value
210 #tree.left = remove(tree.left, tree.value)
211
212 #min = tree.right
213 #min = min.left while min.left
214 #tree.value = min.value
215 #tree.right = remove(tree.right, tree.value)
216 end
217 end
218 tree
219 end
220
221 def delete_from_bst(tree, queries)
222 return nil if tree.nil?
223 queries.each do |target|
224 #puts [target].inspect
225 #tree&.print
226 tree = remove(tree, target)
227 end
228 tree
229 end
230
231 null = nil
232 [
233 { t: { "value": 5, "left": { "value": 2, "left": { "value": 1, "left": null, "right": null }, "right": { "value": 3, "left": null, "right": null } }, "right": { "value": 6, "left": null, "right": { "value": 8, "left": { "value": 7, "left": null, "right": null }, "right": null } } }, queries: [4, 5, 6], x: { "value": 3, "left": { "value": 2, "left": { "value": 1, "left": null, "right": null }, "right": null }, "right": { "value": 8, "left": { "value": 7, "left": null, "right": null }, "right": null } } },
234 { t: null, queries: [1, 2, 3, 5], x: nil },
235 { t: { "value": 3, "left": { "value": 2, "left": null, "right": null }, "right": null }, queries: [1, 2, 3, 5], x: nil },
236 { t: { "value": 3, "left": { "value": 2, "left": null, "right": null }, "right": { "value": 5, "left": null, "right": null } }, queries: [1, 2, 3, 5], x: nil },
237 { t: { "value": 3, "left": { "value": 2, "left": { "value": 1, "left": null, "right": null }, "right": null }, "right": { "value": 5, "left": null, "right": null } }, queries: [3, 2, 1], x: { "value": 5, "left": null, "right": null } },
238 { t: { "value": 5, "left": { "value": 3, "left": { "value": 1, "left": null, "right": null }, "right": { "value": 4, "left": null, "right": null } }, "right": { "value": 7, "left": null, "right": null } }, queries: [1, 7, 4, 6], x: { "value": 5, "left": { "value": 3, "left": null, "right": null }, "right": null } },
239 { t: { value: 3, left: { value: 2, left: { value: 1 } }, right: { value: 6, left: { value: 5 }, right: { value: 8, left: { value: 7 } } } }, queries: [6], x: { value: 3, left: { value: 2, left: { value: 1 } }, right: { value: 5, right: { value: 8, left: { value: 7 } } } } },
240 { t: { "value": 3, "left": { "value": 2, "left": { "value": 1, "left": null, "right": null }, "right": null }, "right": { "value": 5, "left": null, "right": null } }, queries: [3], x: { "value": 2, "left": { "value": 1, "left": null, "right": null }, "right": { "value": 5, "left": null, "right": null } } },
241 { t: null, queries: [100000000, -1000000000, 0, 1, -1, 2, -2], x: null },
242 { t: { "value": 3, "left": { "value": 2, "left": null, "right": null }, "right": { "value": 5, "left": null, "right": null } }, queries: [2, 3, 0, 5], x: nil },
243 ].each do |x|
244 it do
245 result = delete_from_bst(Tree.build_from(x[:t]), x[:queries])
246 expected = x[:x] ? Tree.build_from(x[:x]).to_s : nil
247 expect(result ? result.to_s : result).to eql(expected)
248 end
249 end
250
251 it do
252 require_relative 'spec_8'
253 x = SPEC8
254 result = delete_from_bst(Tree.build_from(x[:t]), x[:queries])
255 expected = x[:x] ? Tree.build_from(x[:x]).to_s : nil
256 expect(result ? result.to_s : result).to eql(expected)
257 end
258
259 it do
260 require_relative 'spec_9'
261 x = SPEC9
262 result = delete_from_bst(Tree.build_from(x[:t]), x[:queries])
263 expected = x[:x] ? Tree.build_from(x[:x]).to_s : nil
264 expect(result.to_s).to eql(expected)
265 end
266
267 it do
268 require_relative 'spec_10'
269 x = SPEC10
270 result = delete_from_bst(Tree.build_from(x[:t]), x[:queries])
271 expected = x[:x] ? Tree.build_from(x[:x]).to_s : nil
272 expect(result.to_s).to eql(expected)
273 end
274end