001package algs32;
002import algs13.Queue;
003import stdlib.*;
004
005/* ***********************************************************************
006 * A simple BST with int keys
007 * 
008 * Recall that:
009 *   Depth of root==0.
010 *   Height of leaf==0.
011 *   Size of empty tree==0.
012 *   Height of empty tree=-1.
013 * 
014 * TODO: complete the functions in this file.
015 *
016 * Restrictions:
017 *  - DO NOT change the Node class.
018 *  - DO NOT change the first line of any function: name, parameters, types.
019 *  - you may add new functions, but don't delete anything
020 *  - functions must be recursive, except printLeftI
021 *  - no loops, except in printLeftI (you cannot use "while" "for" etc...)
022 *  - no fields (variables declared outside of a function)
023 *  - each function must have exactly one recursive helper function, which you add
024 *  - each function must be independent --- do not call any function other than the helper
025 *    (But you may use Math.max)
026 *  
027 * See the method testAll for examples that explain the expected behavior 
028 *************************************************************************/
029public class MyIntSET {
030        private Node root;
031        private static class Node {
032                public final int key;
033                public Node left, right;
034                public Node(int key) { this.key = key; }
035        }
036        
037        // Print only the elements going down the left side of the tree
038        // in the BST with level order traversal "41 21 61 11 31", this should print "41 21 11"
039        public void printLeftI () {
040                // TODO
041        }
042
043        // the number of nodes in the tree
044        // in the BST with level order traversal "41 21 61 11 31", the size is 5
045        public int size() {
046                // TODO
047                return 0;
048        }
049
050        // Recall the definitions of height and depth.
051        // in the BST with level order traversal "41 21 61 11 31",
052        //   node 41 has depth 0, height 2
053        //   node 21 has depth 1, height 1
054        //   node 61 has depth 1, height 0
055        //   node 11 has depth 2, height 0
056        //   node 31 has depth 2, height 0
057        // height of the whole tree is the height of the root
058
059        // the height of the tree
060        public int height() {
061                // TODO
062                return 0;
063        }
064
065        // the number of nodes with odd keys
066        public int sizeOdd() {
067                // TODO
068                return 0;
069        }
070
071        // The next three functions compute the size of the tree at depth k.
072        // It should be the case that for any given k,
073        //
074        //   sizeAbove(k) + sizeAt(k) + sizeBelow(k) = size()
075        //
076        // The words "above" and "below" assume that the root is at the "top".
077        //
078        // Suppose we have with size N and height H (so max depth also H).
079        // For such a tree, we expect
080        //
081        //   sizeAboveDepth (-1)  = 0
082        //   sizeAtDepth    (-1)  = 0
083        //   sizeBelowDepth (-1)  = N
084        //
085        //   sizeAboveDepth (0)   = 0
086        //   sizeAtDepth    (0)   = 1
087        //   sizeBelowDepth (0)   = N-1
088        //
089        //   sizeAboveDepth (H+1) = N
090        //   sizeAtDepth    (H+1) = 0
091        //   sizeBelowDepth (H+1) = 0
092        //
093        // the number of nodes in the tree, at exactly depth k
094        // include node n if depth(n) == k
095        public int sizeAtDepth(int k) {
096                // TODO
097                return 0;
098        }
099
100        // the number of nodes in the tree, "above" depth k (not including k)
101        // include node n if depth(n) < k
102        public int sizeAboveDepth(int k) {
103                // TODO
104                return 0;
105        }
106
107        // the number of nodes in the tree, "below" depth k (not including k)
108        // include node n if depth(n) > k
109        public int sizeBelowDepth(int k) {
110                // TODO
111                return 0;
112        }
113
114        // tree is perfect if for every node, size of left == size of right
115        // hint: in the helper, return -1 if the tree is not perfect, otherwise return the size
116        public boolean isPerfectlyBalancedS() {
117                // TODO
118                return false;
119        }
120
121        // tree is perfect if for every node, height of left == height of right
122        // hint: in the helper, return -2 if the tree is not perfect, otherwise return the height
123        public boolean isPerfectlyBalancedH() {
124                // TODO
125                return false;
126        }
127
128        // tree is odd-perfect if for every node, #odd descendant on left == # odd descendants on right
129        // A node is odd if it has an odd key
130        // hint: in the helper, return -1 if the tree is not odd-perfect, otherwise return the odd size
131        public boolean isOddBalanced() {
132                // TODO
133                return false;
134        }
135
136        // tree is semi-perfect if every node is semi-perfect
137        // A node with 0 children is semi-perfect.
138        // A node with 1 child is NOT semi-perfect.
139        // A node with 2 children is semi-perfect if (size-of-larger-sized-child <= size-of-smaller-sized-child * 3)
140        // Here, larger and smaller have to do with the SIZE of the children, not the key values.
141        // hint: in the helper, return -1 if the tree is not semi-perfect, otherwise return the size
142        public boolean isSemiBalanced() {
143                // TODO
144                return false;
145        }
146
147        /*
148         * Mutator functions
149         * HINT: all of these are easier to write if the helper function returns Node, rather than void.
150         */
151
152        // remove all subtrees with odd roots (if node is odd, remove it and its descendants)
153        // A node is odd if it has an odd key
154        // If the root is odd, then you should end up with the empty tree
155        public void removeOddSubtrees () {
156                // TODO
157        }
158
159        // remove all subtrees below depth k from the original tree
160        public void removeBelowDepth(int k) {
161                // TODO
162        }
163
164        // add a child with key=0 to all nodes that have only one child
165        // (you do not need to retain symmetric order or uniqueness of keys, obviously)
166        public void addZeroToSingles() {
167                // TODO
168        }
169
170        // remove all leaves from the original tree
171        // if you start with "41", then the result is the empty tree.
172        // if you start with "41 21 61", then the result is the tree "41"
173        // if you start with the BST "41 21 11  1", then the result is the tree "41 21 11"
174        // if you start with the BST "41 21 61 11", then the result is the tree "41 21"
175        // Hint: This requires that you check for "leafiness" before the recursive calls
176        public void removeLeaves() {
177                // TODO
178        }
179
180        // remove all nodes that have only one child by "promoting" that child
181        // repeat this recursively as you go up, so the final result should have no nodes with only one child
182        // if you start with "41", the tree is unchanged.
183        // if you start with "41 21 61", the tree is unchanged.
184        // if you start with the BST "41 21 11  1", then the result is the tree "1"
185        // if you start with the BST "41 21 61 11", then the result is the tree "41 11 61"
186        // Hint: This requires that you check for "singleness" after the recursive calls
187        public void removeSingles() {
188                // TODO
189        }
190
191        /* ***************************************************************************
192         *  Test client
193         *  You can modify any of these methods, if you wish
194         *****************************************************************************/
195        public static void main(String[] args) {
196                testOne ();
197                testAccessors ();
198                testMutators ();
199                StdOut.println ("Finished Tests");
200        }
201        private static void testOne () {
202                Trace.drawStepsOfMethod ("printLeftI");
203                Trace.run ();
204                MyIntSET set1 = MyIntSET.fromString("41 21 61 11 31");
205                set1.printLeftI ();
206                //MyIntSET set2 = MyIntSET.fromString ("41 21 61 11 31 51 71 111");
207                //show (set1, "set1");
208                //show (set2, "set2");
209        }
210        private static void testAccessors () {
211                testSize (5, "41 21 61 11 31");
212                testSize (8, "41 21 61 11 31 51 71 111");
213                testSize (9, "101 41 21 61 11 31 51 71 111");
214                testSize (15, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");
215                testSize (11, "101 41 21 61 11 31 51 71 141 121 161");
216                testSize (9, "101 41 21 61 11 31 51 71 141");
217                testSize (15, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");
218                testSize (13, "90 30 100 10 81 20 40 60 50 70 62 63 64");
219                testSize (7, "40 20 61 10 30 50 70");
220                testSize (7, "41 21 61 11 30 51 70");
221                testSize (0, "");
222                testSize (1, "1");
223                testSize (35, "90 30 100 10 80 20 40 60 5 85 35 95 105 2 6 110 103 104 102 93 97 96 82 86 12 21 45 62 106 111 92 94 98 34 36");
224
225                testHeight (2, "41 21 61 11 31");
226                testHeight (3, "41 21 61 11 31 51 71 111");
227                testHeight (3, "101 41 21 61 11 31 51 71 111");
228                testHeight (3, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");
229                testHeight (3, "101 41 21 61 11 31 51 71 141 121 161");
230                testHeight (3, "101 41 21 61 11 31 51 71 141");
231                testHeight (3, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");
232                testHeight (8, "90 30 100 10 81 20 40 60 50 70 62 63 64");
233                testHeight (2, "40 20 61 10 30 50 70");
234                testHeight (2, "41 21 61 11 30 51 70");
235                testHeight (-1, "");
236                testHeight (0, "1");
237                testHeight (5, "90 30 100 10 80 20 40 60 5 85 35 95 105 2 6 110 103 104 102 93 97 96 82 86 12 21 45 62 106 111 92 94 98 34 36");
238
239                testSizeOdd (5, "41 21 61 11 31");
240                testSizeOdd (8, "41 21 61 11 31 51 71 111");
241                testSizeOdd (9, "101 41 21 61 11 31 51 71 111");
242                testSizeOdd (15, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");
243                testSizeOdd (11, "101 41 21 61 11 31 51 71 141 121 161");
244                testSizeOdd (9, "101 41 21 61 11 31 51 71 141");
245                testSizeOdd (11, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");
246                testSizeOdd (2, "90 30 100 10 81 20 40 60 50 70 62 63 64");
247                testSizeOdd (1, "40 20 61 10 30 50 70");
248                testSizeOdd (5, "41 21 61 11 30 51 70");
249                testSizeOdd (0, "");
250                testSizeOdd (1, "1");
251                testSizeOdd (0, "2");
252                testSizeOdd (11, "90 30 100 10 80 20 40 60 5 85 35 95 105 2 6 110 103 104 102 93 97 96 82 86 12 21 45 62 106 111 92 94 98 34 36");
253
254                testSizeAtDepth (2, 2, "41 21 61 11 31");
255                testSizeAtDepth (4, 2, "41 21 61 11 31 51 71 111");
256                testSizeAtDepth (2, 2, "101 41 21 61 11 31 51 71 111");
257                testSizeAtDepth (8, 3, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");
258                testSizeAtDepth (0, 4, "101 41 21 61 11 31 51 71 141 121 161");
259                testSizeAtDepth (2, 2, "101 41 21 61 11 31 51 71 141");
260                testSizeAtDepth (4, 2, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");
261                testSizeAtDepth (2, 3, "90 30 100 10 81 20 40 60 50 70 62 63 64");
262                testSizeAtDepth (4, 2, "40 20 61 10 30 50 70");
263                testSizeAtDepth (2, 1, "41 21 61 11 30 51 70");
264                testSizeAtDepth (0, 2, "");
265                testSizeAtDepth (0, 2, "1");
266                testSizeAtDepth (4, 5, "90 30 100 10 80 20 40 60 5 85 35 95 105 2 6 110 103 104 102 93 97 96 82 86 12 21 45 62 106 111 92 94 98 34 36");
267
268                testSizeAboveDepth (3, 2, "41 21 61 11 31");
269                testSizeAboveDepth (3, 2, "41 21 61 11 31 51 71 111");
270                testSizeAboveDepth (3, 2, "101 41 21 61 11 31 51 71 111");
271                testSizeAboveDepth (7, 3, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");
272                testSizeAboveDepth (11, 4, "101 41 21 61 11 31 51 71 141 121 161");
273                testSizeAboveDepth (3, 2, "101 41 21 61 11 31 51 71 141");
274                testSizeAboveDepth (3, 2, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");
275                testSizeAboveDepth (5, 3, "90 30 100 10 81 20 40 60 50 70 62 63 64");
276                testSizeAboveDepth (3, 2, "40 20 61 10 30 50 70");
277                testSizeAboveDepth (1, 1, "41 21 61 11 30 51 70");
278                testSizeAboveDepth (0, 2, "");
279                testSizeAboveDepth (1, 2, "1");
280                testSizeAboveDepth (31, 5, "90 30 100 10 80 20 40 60 5 85 35 95 105 2 6 110 103 104 102 93 97 96 82 86 12 21 45 62 106 111 92 94 98 34 36");
281
282                testSizeBelowDepth (0, 2, "41 21 61 11 31");
283                testSizeBelowDepth (1, 2, "41 21 61 11 31 51 71 111");
284                testSizeBelowDepth (4, 2, "101 41 21 61 11 31 51 71 111");
285                testSizeBelowDepth (0, 3, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");
286                testSizeBelowDepth (0, 4, "101 41 21 61 11 31 51 71 141 121 161");
287                testSizeBelowDepth (4, 2, "101 41 21 61 11 31 51 71 141");
288                testSizeBelowDepth (8, 2, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");
289                testSizeBelowDepth (6, 3, "90 30 100 10 81 20 40 60 50 70 62 63 64");
290                testSizeBelowDepth (0, 2, "40 20 61 10 30 50 70");
291                testSizeBelowDepth (4, 1, "41 21 61 11 30 51 70");
292                testSizeBelowDepth (0, 2, "");
293                testSizeBelowDepth (0, 2, "1");
294                testSizeBelowDepth (0, 5, "90 30 100 10 80 20 40 60 5 85 35 95 105 2 6 110 103 104 102 93 97 96 82 86 12 21 45 62 106 111 92 94 98 34 36");
295                
296                testIsPerfectlyBalancedS (false, "100 40 140 20 120");
297                testIsPerfectlyBalancedS (true, "17 9 25 5 13 21 29 3 7 11 15 19 23 27 31 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32");
298                testIsPerfectlyBalancedS (false, "17 9 25 5 13 21 29 3 7 11 15 19 23 27 31 4 8 12 16 20 24 28 32");
299                testIsPerfectlyBalancedS (false, "16 8 24 4 12 20 28 2 6 10 14 18 22 26 30 1 5 9 13 17 21 25 29");
300                testIsPerfectlyBalancedS (true, "16 8 24 4 12 20 28 2 6 10 14 18 22 26 30 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31");
301                testIsPerfectlyBalancedS (false, "41 21 61 11 31");
302                testIsPerfectlyBalancedS (false, "41 21 61 11 31 51 71 111");
303                testIsPerfectlyBalancedS (false, "101 41 21 61 11 31 51 71 111");
304                testIsPerfectlyBalancedS (true, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");
305                testIsPerfectlyBalancedS (false, "101 41 21 61 11 31 51 71 141 121 161");
306                testIsPerfectlyBalancedS (false, "101 41 21 61 11 31 51 71 141");
307                testIsPerfectlyBalancedS (true, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");
308                testIsPerfectlyBalancedS (false, "90 30 100 10 81 20 40 60 50 70 62 63 64");
309                testIsPerfectlyBalancedS (true, "40 20 61 10 30 50 70");
310                testIsPerfectlyBalancedS (true, "41 21 61 11 30 51 70");
311                testIsPerfectlyBalancedS (true, "");
312                testIsPerfectlyBalancedS (true, "1");
313                testIsPerfectlyBalancedS (false, "90 30 100 10 80 20 40 60 5 85 35 95 105 2 6 110 103 104 102 93 97 96 82 86 12 21 45 62 106 111 92 94 98 34 36");
314
315                testIsPerfectlyBalancedH (false, "100 40 140 20 120");
316                testIsPerfectlyBalancedH (true, "17 9 25 5 13 21 29 3 7 11 15 19 23 27 31 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32");
317                testIsPerfectlyBalancedH (false, "17 9 25 5 13 21 29 3 7 11 15 19 23 27 31 4 8 12 16 20 24 28 32");
318                testIsPerfectlyBalancedH (false, "16 8 24 4 12 20 28 2 6 10 14 18 22 26 30 1 5 9 13 17 21 25 29");
319                testIsPerfectlyBalancedH (true, "16 8 24 4 12 20 28 2 6 10 14 18 22 26 30 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31");
320                testIsPerfectlyBalancedH (false, "41 21 61 11 31");
321                testIsPerfectlyBalancedH (false, "41 21 61 11 31 51 71 111");
322                testIsPerfectlyBalancedH (false, "101 41 21 61 11 31 51 71 111");
323                testIsPerfectlyBalancedH (true, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");
324                testIsPerfectlyBalancedH (false, "101 41 21 61 11 31 51 71 141 121 161");
325                testIsPerfectlyBalancedH (false, "101 41 21 61 11 31 51 71 141");
326                testIsPerfectlyBalancedH (true, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");
327                testIsPerfectlyBalancedH (false, "90 30 100 10 81 20 40 60 50 70 62 63 64");
328                testIsPerfectlyBalancedH (true, "40 20 61 10 30 50 70");
329                testIsPerfectlyBalancedH (true, "41 21 61 11 30 51 70");
330                testIsPerfectlyBalancedH (true, "");
331                testIsPerfectlyBalancedH (true, "1");
332                testIsPerfectlyBalancedH (false, "90 30 100 10 80 20 40 60 5 85 35 95 105 2 6 110 103 104 102 93 97 96 82 86 12 21 45 62 106 111 92 94 98 34 36");
333
334                testIsOddBalanced (false, "41 21 61 11 31");
335                testIsOddBalanced (false, "41 21 61 11 71");
336                testIsOddBalanced (true, "41 21 61 10 30");
337                testIsOddBalanced (true, "40 21 61");
338                testIsOddBalanced (true, "41 20 60");
339                testIsOddBalanced (false, "41 21 61 11 31 51 71 111");
340                testIsOddBalanced (false, "101 41 21 61 11 31 51 71 111");
341                testIsOddBalanced (true, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");
342                testIsOddBalanced (false, "101 41 21 61 11 31 51 71 141 121 161");
343                testIsOddBalanced (false, "101 41 21 61 11 31 51 71 141");
344                testIsOddBalanced (false, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");
345                testIsOddBalanced (false, "90 30 100 10 81 20 40 60 50 70 62 63 64");
346                testIsOddBalanced (false, "40 20 61 10 30 50 70");
347                testIsOddBalanced (false, "41 21 61 11 30 51 70");
348                testIsOddBalanced (true, "");
349                testIsOddBalanced (true, "1");
350                testIsOddBalanced (false, "90 30 100 10 80 20 40 60 5 85 35 95 105 2 6 110 103 104 102 93 97 96 82 86 12 21 45 62 106 111 92 94 98 34 36");
351
352                testIsSemiBalanced (true, "41 21 61 11 31");
353                testIsSemiBalanced (false, "41 21 61 11 31 51 71 111");
354                testIsSemiBalanced (false, "101 41 21 61 11 31 51 71 111");
355                testIsSemiBalanced (true, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");
356                testIsSemiBalanced (true, "101 41 21 61 11 31 51 71 141 121 161");
357                testIsSemiBalanced (false, "101 41 21 61 11 31 51 71 141");
358                testIsSemiBalanced (true, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");
359                testIsSemiBalanced (false, "90 30 100 10 81 20 40 60 50 70 62 63 64");
360                testIsSemiBalanced (true, "40 20 61 10 30 50 70");
361                testIsSemiBalanced (true, "41 21 61 11 30 51 70");
362                testIsSemiBalanced (true, "");
363                testIsSemiBalanced (true, "1");
364                testIsSemiBalanced (true, "90 30 100 10 80 20 40 60 5 85 35 95 105 2 6 110 103 104 102 93 97 96 82 86 12 21 45 62 106 111 92 94 98 34 36");
365        }
366        private static void testMutators () {
367                testRemoveOddSubtrees ("", "41 21 61 11 31");
368                testRemoveOddSubtrees ("", "101 41 21 61 11 31 51 71 141");
369                testRemoveOddSubtrees ("100 40 140 20 120", "100 40 20 61 11 31 51 71 140 120 161 111 131 151 171");
370                testRemoveOddSubtrees ("90 30 100 10 20", "90 30 100 10 81 20 40 60 50 70 62 63 64");
371                testRemoveOddSubtrees ("40 20 10 30", "40 20 61 10 30 50 70");
372                testRemoveOddSubtrees ("", "41 21 61 11 30 51 70");
373                testRemoveOddSubtrees ("", "");
374                testRemoveOddSubtrees ("", "1");
375                testRemoveOddSubtrees ("0", "0");
376                testRemoveOddSubtrees ("90 30 100 10 80 20 40 12 60 62", "90 30 100 10 80 20 40 60 5 85 35 95 105 2 6 110 103 104 102 93 97 96 82 86 12 21 45 62 106 111 92 94 98 34 36");
377
378                testRemoveBelowDepth ("41 21 61 11 31", 2, "41 21 61 11 31");
379                testRemoveBelowDepth ("41 21 61 11 31 51 71", 2, "41 21 61 11 31 51 71 111");
380                testRemoveBelowDepth ("101 41 111 21 61", 2, "101 41 21 61 11 31 51 71 111");
381                testRemoveBelowDepth ("101 41 141 21 61 121 161", 2, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");
382                testRemoveBelowDepth ("101 41 141 21 61 121 161 11 31 51 71", 4, "101 41 21 61 11 31 51 71 141 121 161");
383                testRemoveBelowDepth ("101 41 141 21 61", 2, "101 41 21 61 11 31 51 71 141");
384                testRemoveBelowDepth ("101 40 140 20 61 120 161", 2, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");
385                testRemoveBelowDepth ("90 30 100 10 81 20 40", 3, "90 30 100 10 81 20 40 60 50 70 62 63 64");
386                testRemoveBelowDepth ("40 20 61 10 30 50 70", 2, "40 20 61 10 30 50 70");
387                testRemoveBelowDepth ("41 21 61", 1, "41 21 61 11 30 51 70");
388                testRemoveBelowDepth ("", 2, "");
389                testRemoveBelowDepth ("1", 2, "1");
390                testRemoveBelowDepth ("90 30 100 10 80 95 105 5 20 40 85 93 97 103 110", 3, "90 30 100 10 80 20 40 60 5 85 35 95 105 2 6 110 103 104 102 93 97 96 82 86 12 21 45 62 106 111 92 94 98 34 36");
391
392                testAddZeroToSingles ("41 21 61 11 0 ", "41 21 61 11");
393                testAddZeroToSingles ("41 21 61 11 0 51 71 ", "41 21 61 11 51 71");
394                testAddZeroToSingles ("90 30 100 10 81 0 20 40 0 0 60 50 70 62 0 0 63 0 64 ", "90 30 100 10 81 20 40 60 50 70 62 63 64");
395                testAddZeroToSingles ("40 20 61 10 30 50 70 ", "40 20 61 10 30 50 70"); 
396                testAddZeroToSingles ("", "");
397                testAddZeroToSingles ("1 ", "1");
398                testAddZeroToSingles ("90 30 100 10 80 95 105 5 20 40 85 93 97 103 110 2 6 12 21 35 60 82 86 92 94 96 98 102 104 106 111 34 36 45 62 ", "90 30 100 10 80 20 40 60 5 85 35 95 105 2 6 110 103 104 102 93 97 96 82 86 12 21 45 62 106 111 92 94 98 34 36");
399
400                testRemoveLeaves ("41 21", "41 21 61 11 31");
401                testRemoveLeaves ("41 21 61 71", "41 21 61 11 31 51 71 111");
402                testRemoveLeaves ("101 41 21 61", "101 41 21 61 11 31 51 71 111");
403                testRemoveLeaves ("101 41 141 21 61 121 161", "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");
404                testRemoveLeaves ("101 41 141 21 61", "101 41 21 61 11 31 51 71 141 121 161");
405                testRemoveLeaves ("101 41 21 61", "101 41 21 61 11 31 51 71 141");
406                testRemoveLeaves ("101 40 140 20 61 120 161", "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");
407                testRemoveLeaves ("90 30 10 81 40 60 70 62 63", "90 30 100 10 81 20 40 60 50 70 62 63 64");
408                testRemoveLeaves ("40 20 61", "40 20 61 10 30 50 70");
409                testRemoveLeaves ("41 21 61", "41 21 61 11 30 51 70");
410                testRemoveLeaves ("", "");
411                testRemoveLeaves ("", "1");
412                testRemoveLeaves ("90 30 100 10 80 95 105 5 20 40 85 93 97 103 110 35 60", "90 30 100 10 80 20 40 60 5 85 35 95 105 2 6 110 103 104 102 93 97 96 82 86 12 21 45 62 106 111 92 94 98 34 36");
413
414                testRemoveSingles ("101 41 141 21 61 121 161 11 31 51 71 111 131 151 171", "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");
415                testRemoveSingles ("101 41 141 21 61 121 161 11 31 51 71", "101 41 21 61 11 31 51 71 141 121 161");
416                testRemoveSingles ("101 41 141 21 61 11 31 51 71", "101 41 21 61 11 31 51 71 141");
417                testRemoveSingles ("101 40 140 20 61 120 161 11 31 51 71 111 131 151 171", "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");
418                testRemoveSingles ("90 30 100 20 60 50 64", "90 30 100 10 81 20 40 60 50 70 62 63 64");
419                testRemoveSingles ("40 20 61 10 30 50 70", "40 20 61 10 30 50 70");
420                testRemoveSingles ("41 21 61 11 30 51 70", "41 21 61 11 30 51 70");
421                testRemoveSingles ("", "");
422                testRemoveSingles ("1", "1");
423                testRemoveSingles ("90 30 100 10 80 95 105 5 20 40 85 93 97 103 110 2 6 12 21 35 60 82 86 92 94 96 98 102 104 106 111 34 36 45 62", "90 30 100 10 80 20 40 60 5 85 35 95 105 2 6 110 103 104 102 93 97 96 82 86 12 21 45 62 106 111 92 94 98 34 36");
424        }
425
426        private static int exampleCount = 0;
427        private static void show(MyIntSET set, String filename) {
428                StdOut.format ("tree x%s-%s: %s\n", exampleCount, filename, set); 
429                set.toGraphviz ("x" + exampleCount + "-" + filename + ".png");
430                exampleCount++;
431        }
432        private static void testSize (int expected, String tree) {
433                MyIntSET set = MyIntSET.fromString(tree);
434                int actual = set.size ();
435                if (! areEquals (set, MyIntSET.fromString(tree))) {
436                        StdOut.format ("Failed size(%s): Tree modified\n", tree);
437                }
438                if (expected != actual) {
439                        StdOut.format ("Failed size(%s): Expecting (%d) Actual (%d)\n", tree, expected, actual);
440                }
441        }
442        private static void testHeight (int expected, String tree) {
443                MyIntSET set = MyIntSET.fromString(tree);
444                int actual = set.height ();
445                if (! areEquals (set, MyIntSET.fromString(tree))) {
446                        StdOut.format ("Failed height(%s): Tree modified\n", tree);
447                }
448                if (expected != actual) {
449                        StdOut.format ("Failed height(%s): Expecting (%d) Actual (%d)\n", tree, expected, actual);
450                }
451        }
452        private static void testSizeOdd (int expected, String tree) {
453                MyIntSET set = MyIntSET.fromString(tree);
454                int actual = set.sizeOdd ();
455                if (! areEquals (set, MyIntSET.fromString(tree))) {
456                        StdOut.format ("Failed sizeOdd(%s): Tree modified\n", tree);
457                }
458                if (expected != actual) {
459                        StdOut.format ("Failed sizeOdd(%s): Expecting (%d) Actual (%d)\n", tree, expected, actual);
460                }
461        }
462        private static void testSizeAtDepth (int expected, int depth, String tree) {
463                MyIntSET set = MyIntSET.fromString(tree);
464                int actual = set.sizeAtDepth (depth);
465                if (! areEquals (set, MyIntSET.fromString(tree))) {
466                        StdOut.format ("Failed sizeAtDepth(%d,%s): Tree modified\n", depth, tree);
467                }
468                if (expected != actual) {
469                        StdOut.format ("Failed sizeAtDepth(%d,%s): Expecting (%d) Actual (%d)\n", depth, tree, expected, actual);
470                }
471        }
472        private static void testSizeAboveDepth (int expected, int depth, String tree) {
473                MyIntSET set = MyIntSET.fromString(tree);
474                int actual = set.sizeAboveDepth (depth);
475                if (! areEquals (set, MyIntSET.fromString(tree))) {
476                        StdOut.format ("Failed sizeAboveDepth(%d,%s): Tree modified\n", depth, tree);
477                }
478                if (expected != actual) {
479                        StdOut.format ("Failed sizeAboveDepth(%d,%s): Expecting (%d) Actual (%d)\n", depth, tree, expected, actual);
480                }
481        }
482        private static void testSizeBelowDepth (int expected, int depth, String tree) {
483                MyIntSET set = MyIntSET.fromString(tree);
484                int actual = set.sizeBelowDepth (depth);
485                if (! areEquals (set, MyIntSET.fromString(tree))) {
486                        StdOut.format ("Failed sizeBelowDepth(%d,%s): Tree modified\n", depth, tree);
487                }
488                if (expected != actual) {
489                        StdOut.format ("Failed sizeBelowDepth(%d,%s): Expecting (%d) Actual (%d)\n", depth, tree, expected, actual);
490                }
491        }
492        private static void testIsPerfectlyBalancedS (boolean expected, String tree) {
493                MyIntSET set = MyIntSET.fromString(tree);
494                boolean actual = set.isPerfectlyBalancedS ();
495                if (! areEquals (set, MyIntSET.fromString(tree))) {
496                        StdOut.format ("Failed isPerfectlyBalancedS(%s): Tree modified\n", tree);
497                }
498                if (expected != actual) {
499                        StdOut.format ("Failed isPerfectlyBalancedS(%s): Expecting (%b) Actual (%b)\n", tree, expected, actual);
500                }
501        }
502        private static void testIsPerfectlyBalancedH (boolean expected, String tree) {
503                MyIntSET set = MyIntSET.fromString(tree);
504                boolean actual = set.isPerfectlyBalancedH ();
505                if (! areEquals (set, MyIntSET.fromString(tree))) {
506                        StdOut.format ("Failed isPerfectlyBalancedH(%s): Tree modified\n", tree);
507                }
508                if (expected != actual) {
509                        StdOut.format ("Failed isPerfectlyBalancedH(%s): Expecting (%b) Actual (%b)\n", tree, expected, actual);
510                }
511        }
512        private static void testIsOddBalanced (boolean expected, String tree) {
513                MyIntSET set = MyIntSET.fromString(tree);
514                boolean actual = set.isOddBalanced ();
515                if (! areEquals (set, MyIntSET.fromString(tree))) {
516                        StdOut.format ("Failed isOddBalanced(%s): Tree modified\n", tree);
517                }
518                if (expected != actual) {
519                        StdOut.format ("Failed isOddBalanced(%s): Expecting (%b) Actual (%b)\n", tree, expected, actual);
520                }
521        }
522        private static void testIsSemiBalanced (boolean expected, String tree) {
523                MyIntSET set = MyIntSET.fromString(tree);
524                boolean actual = set.isSemiBalanced ();
525                if (! areEquals (set, MyIntSET.fromString(tree))) {
526                        StdOut.format ("Failed isSemiBalanced(%s): Tree modified\n", tree);
527                }
528                if (expected != actual) {
529                        StdOut.format ("Failed isSemiBalanced(%s): Expecting (%b) Actual (%b)\n", tree, expected, actual);
530                }
531        }
532        private static void testRemoveOddSubtrees (String expected, String tree) {
533                MyIntSET actual = MyIntSET.fromString(tree);
534                actual.removeOddSubtrees ();            
535                if (! areEquals (actual, MyIntSET.fromString(expected))) {
536                        StdOut.format ("Failed removeOddSubtrees\n");
537                        show (MyIntSET.fromString(tree), "original");
538                        show (actual, "actual");
539                        show (MyIntSET.fromString(expected), "expected");
540                }
541        }       
542        private static void testRemoveBelowDepth (String expected, int depth, String tree) {
543                MyIntSET actual = MyIntSET.fromString(tree);
544                actual.removeBelowDepth (depth);                
545                if (! areEquals (actual, MyIntSET.fromString(expected))) {
546                        StdOut.format ("Failed removeBelowDepth(%d)\n", depth);
547                        show (MyIntSET.fromString(tree), "original");
548                        show (actual, "actual");
549                        show (MyIntSET.fromString(expected), "expected");
550                }
551        }
552        private static void testRemoveSingles (String expected, String tree) {
553                MyIntSET actual = MyIntSET.fromString(tree);
554                actual.removeSingles ();                
555                if (! areEquals (actual, MyIntSET.fromString(expected))) {
556                        StdOut.format ("Failed removeSingles\n");
557                        show (MyIntSET.fromString(tree), "original");
558                        show (actual, "actual");
559                        show (MyIntSET.fromString(expected), "expected");
560                }
561        }
562        private static void testRemoveLeaves(String expected, String tree) {
563                MyIntSET actual = MyIntSET.fromString(tree);
564                actual.removeLeaves();          
565                if (! areEquals (actual, MyIntSET.fromString(expected))) {
566                        StdOut.format ("Failed removeLeaves\n");
567                        show (MyIntSET.fromString(tree), "original");
568                        show (actual, "actual");
569                        show (MyIntSET.fromString(expected), "expected");
570                }
571        }
572        private static void testAddZeroToSingles(String expected, String tree) {
573                MyIntSET actual = MyIntSET.fromString(tree);
574                actual.addZeroToSingles ();
575                if (! expected.equals (actual.toString ())) {
576                        StdOut.format ("Failed addZeroToSingles\n");
577                        show (MyIntSET.fromString(tree), "original");
578                        show (actual, "actual");
579                        show (MyIntSET.fromString(expected), "expected");
580                }
581        }
582
583        /* ***************************************************************************
584         * Some methods to create and display trees
585         * DO NOT MODIFY THESE METHODS
586         *****************************************************************************/
587        // Add one element to a tree, in BST order
588        public void put(int key) { root = put(root, key); }
589        private static Node put(Node n, int key) {
590                if (n == null) return new Node(key);
591                if      (key < n.key) n.left  = put(n.left,  key);
592                else if (key > n.key) n.right = put(n.right, key);
593                return n;
594        }
595        // Test for equality
596        public static boolean areEquals (MyIntSET a, MyIntSET b) { return areEquals(a.root, b.root); }
597        private static boolean areEquals (Node x, Node y) {
598                if (x == null) {
599                        return (y == null);
600                } else {
601                        return (y != null) && x.key == y.key && areEquals (x.left, y.left) && areEquals (x.right, y.right);
602                }               
603        }
604        // Create a tree from a string
605        public static MyIntSET fromString (String ints) {
606                MyIntSET set = new MyIntSET ();
607                for (String s : ints.split (" "))
608                        try { set.put (Integer.parseInt (s)); } catch (NumberFormatException e) {}
609                return set;
610        }
611        // Return the values of the tree in level order
612        public Iterable<Integer> levelOrder() {
613                Queue<Integer> keys = new Queue<>();
614                Queue<Node> queue = new Queue<>();
615                queue.enqueue(root);
616                while (!queue.isEmpty()) {
617                        Node n = queue.dequeue();
618                        if (n == null) continue;
619                        keys.enqueue(n.key);
620                        queue.enqueue(n.left);
621                        queue.enqueue(n.right);
622                }
623                return keys;
624        }
625        // String representation of the tree
626        public String toString() {
627                StringBuilder sb = new StringBuilder();
628                for (int key: levelOrder())
629                        sb.append (key + " ");
630                return sb.toString ();
631        }
632        // Graphical representation of the tree
633        public void toGraphviz(String filename) {
634                GraphvizBuilder gb = new GraphvizBuilder ();
635                toGraphviz (gb, null, root);
636                gb.toFileUndirected (filename, "ordering=\"out\"");
637        }
638        private static void toGraphviz (GraphvizBuilder gb, Node parent, Node n) {
639                if (n == null) { gb.addNullEdge (parent); return; }
640                gb.addLabeledNode (n, Integer.toString (n.key));
641                if (parent != null) gb.addEdge (parent, n);
642                toGraphviz (gb, n, n.left);
643                toGraphviz (gb, n, n.right);
644        }
645}