IN JAVA, PLEASE COMPLETE THE FOLLOWING TO DO LIST AND PLEASE MAKE SURE THE PROGRAM COMPILES PERFECTLY.

Recall that:

* Depth of root==0.

* Height of leaf==0.

* Size of empty tree==0.

* Height of empty tree=-1.

*

* TODO: complete the functions in this file.

*

* Restrictions:

* - DO NOT change the Node class.

* - DO NOT change the first line of any function: name, parameters, types.

* - you may add new functions, but don't delete anything

* - functions must be recursive, except printLeftI

* - no loops, except in printLeftI (you cannot use "while" "for" etc...)

* - each function must have exactly one recursive helper function, which you add

* - each function must be independent --- do not call any function other than the helper

* - no fields (variables declared outside of a function)

*

* See the method testAll for examples that explain the expected behavior

*************************************************************************/

public class MyIntSET {

private Node root;

private static class Node {

public final int key;

public Node left, right;

public Node(int key) { this.key = key; }

}

// Print only the elements going down the left side of the tree

// in the BST with level order traversal "41 21 61 11 31", this should print "41 21 11"

public void printLeftI () {

// TODO

}

// the number of nodes in the tree

// in the BST with level order traversal "41 21 61 11 31", the size is 5

int size()

{return size(root);}

int size(Node node)

{

if (node == null)

return 0;

else

return(size(node.left) + 1 + size(node.right));

}

int height(){

return height(root);

}

int height(Node node)

{

if (node == null)

return 0;

else{

int lheight = height(node.left);

int rheight = height(node.right);

if (lheight > rheight)

return (lheight + 1);

else

return (rheight + 1);

}}

int sizeOdd(){

return sizeOdd(root);

}

int sizeOdd(Node node){

int result=0,resultleft=0,resultright = 0;

if(node != null){

if(node.key % 2 == 1){

result = result+1;

}

resultleft=sizeOdd(node.left);

resultright=sizeOdd(node.right);

}

return result+ resultleft + resultright;

}

int sizeAtDepth(int k){

return sizeAtDepth(root,0,k);

}

public int sizeAtDepth(Node node, int depth, final int k) {

if ( node!= null && depth == k){

return sizeAtDepth( node.left, depth+1, k) +

sizeAtDepth( node.right, depth+1, k) + 1;

} else {

return 0;

} }

int sizeAboveDepth(int k){

return sizeAboveDepth(root,0,k);

}

public static int sizeAboveDepth(Node t, int depth, final int k) {

if ( t != null && depth < k){

return sizeAboveDepth( t.left, depth+1, k) +

sizeAboveDepth( t.right, depth+1, k) + 1;

} else {

return 0;

} }

int sizeBelowDepth(int k){

return sizeBelowDepth(root,0,k);

}

public static int sizeBelowDepth(Node t, int depth, final int k) {

if (t == null) {

return 0;

}

int below = sizeBelowDepth(t.left, depth+1, k) +

sizeBelowDepth(t.right, depth+1, k);

if (depth > k){

below++;

}

return below;}

public boolean isPerfectlyBalancedH(){

return isPerfectlyBalancedH(root);

}

public boolean isPerfectlyBalancedH(Node node)

{

int lh;

int rh;

if (node == null)

return true;

lh = height(node.left);

rh = height(node.right);

if (Math.abs(lh - rh) <= 1 && isPerfectlyBalancedH(node.left) && isPerfectlyBalancedH(node.right))

return true;

return false;

}

public boolean isPerfectlyBalancedS(){

return isPerfectlyBalancedS(root);

}

public boolean isPerfectlyBalancedS(Node node)

{

int ls;

int rs;

if (node == null)

return true;

ls = size(node.left);

rs = size(node.right);

if (Math.abs(ls - rs) <= 1

&& isPerfectlyBalancedS(node.left)

&& isPerfectlyBalancedS(node.right))

return true;

return false;

}

// public int size() {

// // TODO

// return 0;

// }

// // Recall the definitions of height and depth.

// // in the BST with level order traversal "41 21 61 11 31",

// // node 41 has depth 0, height 2

// // node 21 has depth 1, height 1

// // node 61 has depth 1, height 0

// // node 11 has depth 2, height 0

// // node 31 has depth 2, height 0

// // height of the whole tree is the height of the root

// // the height of the tree

// public int height() {

// // TODO

// return 0;

// }

// // the number of nodes with odd keys

// public int sizeOdd() {

// // TODO

// return 0;

// }

// // The next three functions compute the size of the tree at depth k.

// // It should be the case that for any given k,

// //

// // sizeAbove(k) + sizeAt(k) + sizeBelow(k) = size()

// //

// // The words "above" and "below" assume that the root is at the "top".

// //

// // Suppose we have with size N and height H (so max depth also H).

// // For such a tree, we expect

// //

// // sizeAboveDepth (-1) = 0

// // sizeAtDepth (-1) = 0

// // sizeBelowDepth (-1) = N

// //

// // sizeAboveDepth (0) = 0

// // sizeAtDepth (0) = 1

// // sizeBelowDepth (0) = N-1

// //

// // sizeAboveDepth (H+1) = N

// // sizeAtDepth (H+1) = 0

// // sizeBelowDepth (H+1) = 0

// //

// // the number of nodes in the tree, at exactly depth k

// // include node n if depth(n) == k

// public int sizeAtDepth(int k) {

// // TODO

// return 0;

// }

// // the number of nodes in the tree, "above" depth k (not including k)

// // include node n if depth(n) < k

// public int sizeAboveDepth(int k) {

// // TODO

// return 0;

// }

// // the number of nodes in the tree, "below" depth k (not including k)

// // include node n if depth(n) > k

// public int sizeBelowDepth(int k) {

// // TODO

// return 0;

// }

// // tree is perfect if for every node, size of left == size of right

// // hint: in the helper, return -1 if the tree is not perfect, otherwise return the size

// public boolean isPerfectlyBalancedS() {

// // TODO

// return false;

// }

// // tree is perfect if for every node, height of left == height of right

// // hint: in the helper, return -2 if the tree is not perfect, otherwise return the height

// public boolean isPerfectlyBalancedH() {

// // TODO

// return false;

// }

// tree is odd-perfect if for every node, #odd descendant on left == # odd descendants on right

// A node is odd if it has an odd key

// hint: in the helper, return -1 if the tree is not odd-perfect, otherwise return the odd size

public boolean isOddBalanced() {

// TODO

return false;

}

// tree is semi-perfect if every node is semi-perfect

// A node with 0 children is semi-perfect.

// A node with 1 child is NOT semi-perfect.

// A node with 2 children is semi-perfect if (size-of-larger-sized-child <= size-of-smaller-sized-child * 3)

// Here, larger and smaller have to do with the SIZE of the children, not the key values.

// hint: in the helper, return -1 if the tree is not semi-perfect, otherwise return the size

public boolean isSemiBalanced() {

// TODO

return false;

}

/*

* Mutator functions

* HINT: all of these are easier to write if the helper function returns Node, rather than void.

*/

// remove all subtrees with odd roots (if node is odd, remove it and its descendants)

// A node is odd if it has an odd key

// If the root is odd, then you should end up with the empty tree

public void removeOddSubtrees () {

// TODO

}

// remove all subtrees below depth k from the original tree

public void removeBelowDepth(int k) {

// TODO

}

// add a child with key=0 to all nodes that have only one child

// (you do not need to retain symmetric order or uniqueness of keys, obviously)

public void addZeroToSingles() {

// TODO

}

// remove all leaves from the original tree

// if you start with "41", then the result is the empty tree.

// if you start with "41 21 61", then the result is the tree "41"

// if you start with the BST "41 21 11 1", then the result is the tree "41 21 11"

// if you start with the BST "41 21 61 11", then the result is the tree "41 21"

// Hint: This requires that you check for "leafiness" before the recursive calls

public void removeLeaves() {

// TODO

}

// remove all nodes that have only one child by "promoting" that child

// repeat this recursively as you go up, so the final result should have no nodes with only one child

// if you start with "41", the tree is unchanged.

// if you start with "41 21 61", the tree is unchanged.

// if you start with the BST "41 21 11 1", then the result is the tree "1"

// if you start with the BST "41 21 61 11", then the result is the tree "41 11 61"

// Hint: This requires that you check for "singleness" after the recursive calls

public void removeSingles() {

// TODO

}

/* ***************************************************************************

* Test client

* You can modify any of these methods, if you wish

*****************************************************************************/

public static void main(String[] args) {

testOne ();

testAll ();

//runAll ("");

//runAll ("1");

//runAll ("41 21 61 11 31");

//runAll ("41 21 61 11 30 51 70");

//runAll ("40 20 61 10 30 50 70");

//runAll ("41 21 61 11 31 51 71 111");

//runAll ("101 41 21 61 11 31 51 71 111");

//runAll ("101 41 21 61 11 31 51 71 141");

//runAll ("101 41 21 61 11 31 51 71 141 121 161");

//runAll ("101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");

//runAll ("101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");

//runAll ("90 30 100 10 81 20 40 60 50 70 62 63 64");

//runAll ("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");

//runAll ("17 9 25 5 13 21 29 3 7 11 15 19 23 27 31 4 8 12 16 20 24 28 32");

//runAll ("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");

//runAll ("16 8 24 4 12 20 28 2 6 10 14 18 22 26 30 1 5 9 13 17 21 25 29");

//runAll ("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");

}

private static void testOne () {

//Trace.drawStepsOfMethod ("printLeftI");

//Trace.run ();

MyIntSET set1 = MyIntSET.fromString("41 21 61 11 31");

set1.printLeftI ();

//MyIntSET set2 = MyIntSET.fromString ("41 21 61 11 31 51 71 111");

//show (set1, "set1");

//show (set2, "set2");

}

private static void testAll () {

testSize (5, "41 21 61 11 31");

testSize (8, "41 21 61 11 31 51 71 111");

testSize (9, "101 41 21 61 11 31 51 71 111");

testSize (15, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");

testSize (11, "101 41 21 61 11 31 51 71 141 121 161");

testSize (9, "101 41 21 61 11 31 51 71 141");

testSize (15, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");

testSize (13, "90 30 100 10 81 20 40 60 50 70 62 63 64");

testSize (7, "40 20 61 10 30 50 70");

testSize (7, "41 21 61 11 30 51 70");

testSize (0, "");

testSize (1, "1");

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");

testHeight (2, "41 21 61 11 31");

testHeight (3, "41 21 61 11 31 51 71 111");

testHeight (3, "101 41 21 61 11 31 51 71 111");

testHeight (3, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");

testHeight (3, "101 41 21 61 11 31 51 71 141 121 161");

testHeight (3, "101 41 21 61 11 31 51 71 141");

testHeight (3, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");

testHeight (8, "90 30 100 10 81 20 40 60 50 70 62 63 64");

testHeight (2, "40 20 61 10 30 50 70");

testHeight (2, "41 21 61 11 30 51 70");

testHeight (-1, "");

testHeight (0, "1");

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");

testSizeOdd (5, "41 21 61 11 31");

testSizeOdd (8, "41 21 61 11 31 51 71 111");

testSizeOdd (9, "101 41 21 61 11 31 51 71 111");

testSizeOdd (15, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");

testSizeOdd (11, "101 41 21 61 11 31 51 71 141 121 161");

testSizeOdd (9, "101 41 21 61 11 31 51 71 141");

testSizeOdd (11, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");

testSizeOdd (2, "90 30 100 10 81 20 40 60 50 70 62 63 64");

testSizeOdd (1, "40 20 61 10 30 50 70");

testSizeOdd (5, "41 21 61 11 30 51 70");

testSizeOdd (0, "");

testSizeOdd (1, "1");

testSizeOdd (0, "2");

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");

testSizeAtDepth (2, 2, "41 21 61 11 31");

testSizeAtDepth (4, 2, "41 21 61 11 31 51 71 111");

testSizeAtDepth (2, 2, "101 41 21 61 11 31 51 71 111");

testSizeAtDepth (8, 3, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");

testSizeAtDepth (0, 4, "101 41 21 61 11 31 51 71 141 121 161");

testSizeAtDepth (2, 2, "101 41 21 61 11 31 51 71 141");

testSizeAtDepth (4, 2, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");

testSizeAtDepth (2, 3, "90 30 100 10 81 20 40 60 50 70 62 63 64");

testSizeAtDepth (4, 2, "40 20 61 10 30 50 70");

testSizeAtDepth (2, 1, "41 21 61 11 30 51 70");

testSizeAtDepth (0, 2, "");

testSizeAtDepth (0, 2, "1");

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");

testSizeAboveDepth (3, 2, "41 21 61 11 31");

testSizeAboveDepth (3, 2, "41 21 61 11 31 51 71 111");

testSizeAboveDepth (3, 2, "101 41 21 61 11 31 51 71 111");

testSizeAboveDepth (7, 3, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");

testSizeAboveDepth (11, 4, "101 41 21 61 11 31 51 71 141 121 161");

testSizeAboveDepth (3, 2, "101 41 21 61 11 31 51 71 141");

testSizeAboveDepth (3, 2, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");

testSizeAboveDepth (5, 3, "90 30 100 10 81 20 40 60 50 70 62 63 64");

testSizeAboveDepth (3, 2, "40 20 61 10 30 50 70");

testSizeAboveDepth (1, 1, "41 21 61 11 30 51 70");

testSizeAboveDepth (0, 2, "");

testSizeAboveDepth (1, 2, "1");

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");

testSizeBelowDepth (0, 2, "41 21 61 11 31");

testSizeBelowDepth (1, 2, "41 21 61 11 31 51 71 111");

testSizeBelowDepth (4, 2, "101 41 21 61 11 31 51 71 111");

testSizeBelowDepth (0, 3, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");

testSizeBelowDepth (0, 4, "101 41 21 61 11 31 51 71 141 121 161");

testSizeBelowDepth (4, 2, "101 41 21 61 11 31 51 71 141");

testSizeBelowDepth (8, 2, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");

testSizeBelowDepth (6, 3, "90 30 100 10 81 20 40 60 50 70 62 63 64");

testSizeBelowDepth (0, 2, "40 20 61 10 30 50 70");

testSizeBelowDepth (4, 1, "41 21 61 11 30 51 70");

testSizeBelowDepth (0, 2, "");

testSizeBelowDepth (0, 2, "1");

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");

testIsPerfectlyBalancedS (false, "100 40 140 20 120");

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");

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");

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");

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");

testIsPerfectlyBalancedS (false, "41 21 61 11 31");

testIsPerfectlyBalancedS (false, "41 21 61 11 31 51 71 111");

testIsPerfectlyBalancedS (false, "101 41 21 61 11 31 51 71 111");

testIsPerfectlyBalancedS (true, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");

testIsPerfectlyBalancedS (false, "101 41 21 61 11 31 51 71 141 121 161");

testIsPerfectlyBalancedS (false, "101 41 21 61 11 31 51 71 141");

testIsPerfectlyBalancedS (true, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");

testIsPerfectlyBalancedS (false, "90 30 100 10 81 20 40 60 50 70 62 63 64");

testIsPerfectlyBalancedS (true, "40 20 61 10 30 50 70");

testIsPerfectlyBalancedS (true, "41 21 61 11 30 51 70");

testIsPerfectlyBalancedS (true, "");

testIsPerfectlyBalancedS (true, "1");

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");

testIsPerfectlyBalancedH (false, "100 40 140 20 120");

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");

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");

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");

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");

testIsPerfectlyBalancedH (false, "41 21 61 11 31");

testIsPerfectlyBalancedH (false, "41 21 61 11 31 51 71 111");

testIsPerfectlyBalancedH (false, "101 41 21 61 11 31 51 71 111");

testIsPerfectlyBalancedH (true, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");

testIsPerfectlyBalancedH (false, "101 41 21 61 11 31 51 71 141 121 161");

testIsPerfectlyBalancedH (false, "101 41 21 61 11 31 51 71 141");

testIsPerfectlyBalancedH (true, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");

testIsPerfectlyBalancedH (false, "90 30 100 10 81 20 40 60 50 70 62 63 64");

testIsPerfectlyBalancedH (true, "40 20 61 10 30 50 70");

testIsPerfectlyBalancedH (true, "41 21 61 11 30 51 70");

testIsPerfectlyBalancedH (true, "");

testIsPerfectlyBalancedH (true, "1");

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");

testIsOddBalanced (false, "41 21 61 11 31");

testIsOddBalanced (false, "41 21 61 11 71");

testIsOddBalanced (true, "41 21 61 10 30");

testIsOddBalanced (true, "40 21 61");

testIsOddBalanced (true, "41 20 60");

testIsOddBalanced (false, "41 21 61 11 31 51 71 111");

testIsOddBalanced (false, "101 41 21 61 11 31 51 71 111");

testIsOddBalanced (true, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");

testIsOddBalanced (false, "101 41 21 61 11 31 51 71 141 121 161");

testIsOddBalanced (false, "101 41 21 61 11 31 51 71 141");

testIsOddBalanced (false, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");

testIsOddBalanced (false, "90 30 100 10 81 20 40 60 50 70 62 63 64");

testIsOddBalanced (false, "40 20 61 10 30 50 70");

testIsOddBalanced (false, "41 21 61 11 30 51 70");

testIsOddBalanced (true, "");

testIsOddBalanced (true, "1");

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");

testIsSemiBalanced (true, "41 21 61 11 31");

testIsSemiBalanced (false, "41 21 61 11 31 51 71 111");

testIsSemiBalanced (false, "101 41 21 61 11 31 51 71 111");

testIsSemiBalanced (true, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");

testIsSemiBalanced (true, "101 41 21 61 11 31 51 71 141 121 161");

testIsSemiBalanced (false, "101 41 21 61 11 31 51 71 141");

testIsSemiBalanced (true, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");

testIsSemiBalanced (false, "90 30 100 10 81 20 40 60 50 70 62 63 64");

testIsSemiBalanced (true, "40 20 61 10 30 50 70");

testIsSemiBalanced (true, "41 21 61 11 30 51 70");

testIsSemiBalanced (true, "");

testIsSemiBalanced (true, "1");

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");

testRemoveOddSubtrees ("", "41 21 61 11 31");

testRemoveOddSubtrees ("", "101 41 21 61 11 31 51 71 141");

testRemoveOddSubtrees ("100 40 140 20 120", "100 40 20 61 11 31 51 71 140 120 161 111 131 151 171");

testRemoveOddSubtrees ("90 30 100 10 20", "90 30 100 10 81 20 40 60 50 70 62 63 64");

testRemoveOddSubtrees ("40 20 10 30", "40 20 61 10 30 50 70");

testRemoveOddSubtrees ("", "41 21 61 11 30 51 70");

testRemoveOddSubtrees ("", "");

testRemoveOddSubtrees ("", "1");

testRemoveOddSubtrees ("0", "0");

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");

testRemoveBelowDepth ("41 21 61 11 31", 2, "41 21 61 11 31");

testRemoveBelowDepth ("41 21 61 11 31 51 71", 2, "41 21 61 11 31 51 71 111");

testRemoveBelowDepth ("101 41 111 21 61", 2, "101 41 21 61 11 31 51 71 111");

testRemoveBelowDepth ("101 41 141 21 61 121 161", 2, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");

testRemoveBelowDepth ("101 41 141 21 61 121 161 11 31 51 71", 4, "101 41 21 61 11 31 51 71 141 121 161");

testRemoveBelowDepth ("101 41 141 21 61", 2, "101 41 21 61 11 31 51 71 141");

testRemoveBelowDepth ("101 40 140 20 61 120 161", 2, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");

testRemoveBelowDepth ("90 30 100 10 81 20 40", 3, "90 30 100 10 81 20 40 60 50 70 62 63 64");

testRemoveBelowDepth ("40 20 61 10 30 50 70", 2, "40 20 61 10 30 50 70");

testRemoveBelowDepth ("41 21 61", 1, "41 21 61 11 30 51 70");

testRemoveBelowDepth ("", 2, "");

testRemoveBelowDepth ("1", 2, "1");

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");

testAddZeroToSingles ("41 21 61 11 0 ", "41 21 61 11");

testAddZeroToSingles ("41 21 61 11 0 51 71 ", "41 21 61 11 51 71");

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");

testAddZeroToSingles ("40 20 61 10 30 50 70 ", "40 20 61 10 30 50 70");

testAddZeroToSingles ("", "");

testAddZeroToSingles ("1 ", "1");

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");

testRemoveLeaves ("41 21", "41 21 61 11 31");

testRemoveLeaves ("41 21 61 71", "41 21 61 11 31 51 71 111");

testRemoveLeaves ("101 41 21 61", "101 41 21 61 11 31 51 71 111");

testRemoveLeaves ("101 41 141 21 61 121 161", "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171");

testRemoveLeaves ("101 41 141 21 61", "101 41 21 61 11 31 51 71 141 121 161");

testRemoveLeaves ("101 41 21 61", "101 41 21 61 11 31 51 71 141");

testRemoveLeaves ("101 40 140 20 61 120 161", "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171");

testRemoveLeaves ("90 30 10 81 40 60 70 62 63", "90 30 100 10 81 20 40 60 50 70 62 63 64");

testRemoveLeaves ("40 20 61", "40 20 61 10 30 50 70");

testRemoveLeaves ("41 21 61", "41 21 61 11 30 51 70");

testRemoveLeaves ("", "");

testRemoveLeaves ("", "1");

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");

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");

testRemoveSingles ("101 41 141 21 61 121 161 11 31 51 71", "101 41 21 61 11 31 51 71 141 121 161");

testRemoveSingles ("101 41 141 21 61 11 31 51 71", "101 41 21 61 11 31 51 71 141");

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");

testRemoveSingles ("90 30 100 20 60 50 64", "90 30 100 10 81 20 40 60 50 70 62 63 64");

testRemoveSingles ("40 20 61 10 30 50 70", "40 20 61 10 30 50 70");

testRemoveSingles ("41 21 61 11 30 51 70", "41 21 61 11 30 51 70");

testRemoveSingles ("", "");

testRemoveSingles ("1", "1");

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");

StdOut.println ("Finished Tests");

}

private static void runAll(String s) {

MyIntSET set = MyIntSET.fromString(s);

StdOut.println ("###############################################################");

show(set, "original");

StdOut.format ("size() = %d ", set.size());

StdOut.format ("height() = %d ", set.height());

StdOut.format ("sizeOdd() = %d ", set.sizeOdd());

StdOut.format ("sizeAtDepth(2) = %d ", set.sizeAtDepth(2));

StdOut.format ("sizeAboveDepth(2) = %d ", set.sizeAboveDepth(2));

StdOut.format ("sizeBelowDepth(2) = %d ", set.sizeBelowDepth(2));

StdOut.format ("isPerfectlyBalancedS() = %b ", set.isPerfectlyBalancedS());

StdOut.format ("isPerfectlyBalancedH() = %b ", set.isPerfectlyBalancedH());

StdOut.format ("isOddBalanced() = %b ", set.isOddBalanced());

StdOut.format ("isSemiBalanced() = %b ", set.isSemiBalanced());

set = MyIntSET.fromString(s); set.removeOddSubtrees(); StdOut.format ("removeOddSubtrees() %s ", set); show(set, "removeOddSubtrees");

set = MyIntSET.fromString(s); set.removeBelowDepth(2); StdOut.format ("removeBelowDepth(2) %s ", set); show(set, "removeBelowDepth2");

set = MyIntSET.fromString(s); set.removeLeaves(); StdOut.format ("removeLeaves() %s ", set); show(set, "removeLeaves");

set = MyIntSET.fromString(s); set.removeSingles(); StdOut.format ("removeSingles() %s ", set); show(set, "removeSingles");

set = MyIntSET.fromString(s); set.addZeroToSingles(); StdOut.format ("addZeroToSingles() %s ", set); show(set, "addZeroToSingles");

}

private static int exampleCount = 0;

private static void show(MyIntSET set, String filename) {

StdOut.format ("tree x%s-%s: %s ", exampleCount, filename, set);

set.toGraphviz ("x" + exampleCount + "-" + filename + ".png");

exampleCount++;

}

private static void testSize (int expected, String tree) {

MyIntSET set = MyIntSET.fromString(tree);

int actual = set.size ();

if (! areEquals (set, MyIntSET.fromString(tree))) {

StdOut.format ("Failed size(%s): Tree modified ", tree);

}

if (expected != actual) {

StdOut.format ("Failed size(%s): Expecting (%d) Actual (%d) ", tree, expected, actual);

}

}

private static void testHeight (int expected, String tree) {

MyIntSET set = MyIntSET.fromString(tree);

int actual = set.height ();

if (! areEquals (set, MyIntSET.fromString(tree))) {

StdOut.format ("Failed height(%s): Tree modified ", tree);

}

if (expected != actual) {

StdOut.format ("Failed height(%s): Expecting (%d) Actual (%d) ", tree, expected, actual);

}

}

private static void testSizeOdd (int expected, String tree) {

MyIntSET set = MyIntSET.fromString(tree);

int actual = set.sizeOdd ();

if (! areEquals (set, MyIntSET.fromString(tree))) {

StdOut.format ("Failed sizeOdd(%s): Tree modified ", tree);

}

if (expected != actual) {

StdOut.format ("Failed sizeOdd(%s): Expecting (%d) Actual (%d) ", tree, expected, actual);

}

}

private static void testSizeAtDepth (int expected, int depth, String tree) {

MyIntSET set = MyIntSET.fromString(tree);

int actual = set.sizeAtDepth (depth);

if (! areEquals (set, MyIntSET.fromString(tree))) {

StdOut.format ("Failed sizeAtDepth(%d,%s): Tree modified ", depth, tree);

}

if (expected != actual) {

StdOut.format ("Failed sizeAtDepth(%d,%s): Expecting (%d) Actual (%d) ", depth, tree, expected, actual);

}

}

private static void testSizeAboveDepth (int expected, int depth, String tree) {

MyIntSET set = MyIntSET.fromString(tree);

int actual = set.sizeAboveDepth (depth);

if (! areEquals (set, MyIntSET.fromString(tree))) {

StdOut.format ("Failed sizeAboveDepth(%d,%s): Tree modified ", depth, tree);

}

if (expected != actual) {

StdOut.format ("Failed sizeAboveDepth(%d,%s): Expecting (%d) Actual (%d) ", depth, tree, expected, actual);

}

}

private static void testSizeBelowDepth (int expected, int depth, String tree) {

MyIntSET set = MyIntSET.fromString(tree);

int actual = set.sizeBelowDepth (depth);

if (! areEquals (set, MyIntSET.fromString(tree))) {

StdOut.format ("Failed sizeBelowDepth(%d,%s): Tree modified ", depth, tree);

}

if (expected != actual) {

StdOut.format ("Failed sizeBelowDepth(%d,%s): Expecting (%d) Actual (%d) ", depth, tree, expected, actual);

}

}

private static void testIsPerfectlyBalancedS (boolean expected, String tree) {

MyIntSET set = MyIntSET.fromString(tree);

boolean actual = set.isPerfectlyBalancedS ();

if (! areEquals (set, MyIntSET.fromString(tree))) {

StdOut.format ("Failed isPerfectlyBalancedS(%s): Tree modified ", tree);

}

if (expected != actual) {

StdOut.format ("Failed isPerfectlyBalancedS(%s): Expecting (%b) Actual (%b) ", tree, expected, actual);

}

}

private static void testIsPerfectlyBalancedH (boolean expected, String tree) {

MyIntSET set = MyIntSET.fromString(tree);

boolean actual = set.isPerfectlyBalancedH ();

if (! areEquals (set, MyIntSET.fromString(tree))) {

StdOut.format ("Failed isPerfectlyBalancedH(%s): Tree modified ", tree);

}

if (expected != actual) {

StdOut.format ("Failed isPerfectlyBalancedH(%s): Expecting (%b) Actual (%b) ", tree, expected, actual);

}

}

private static void testIsOddBalanced (boolean expected, String tree) {

MyIntSET set = MyIntSET.fromString(tree);

boolean actual = set.isOddBalanced ();

if (! areEquals (set, MyIntSET.fromString(tree))) {

StdOut.format ("Failed isOddBalanced(%s): Tree modified ", tree);

}

if (expected != actual) {

StdOut.format ("Failed isOddBalanced(%s): Expecting (%b) Actual (%b) ", tree, expected, actual);

}

}

private static void testIsSemiBalanced (boolean expected, String tree) {

MyIntSET set = MyIntSET.fromString(tree);

boolean actual = set.isSemiBalanced ();

if (! areEquals (set, MyIntSET.fromString(tree))) {

StdOut.format ("Failed isSemiBalanced(%s): Tree modified ", tree);

}

if (expected != actual) {

StdOut.format ("Failed isSemiBalanced(%s): Expecting (%b) Actual (%b) ", tree, expected, actual);

}

}

private static void testRemoveOddSubtrees (String expected, String tree) {

MyIntSET actual = MyIntSET.fromString(tree);

actual.removeOddSubtrees ();

if (! areEquals (actual, MyIntSET.fromString(expected))) {

StdOut.format ("Failed removeOddSubtrees ");

show (MyIntSET.fromString(tree), "original");

show (actual, "actual");

show (MyIntSET.fromString(expected), "expected");

}

}

private static void testRemoveBelowDepth (String expected, int depth, String tree) {

MyIntSET actual = MyIntSET.fromString(tree);

actual.removeBelowDepth (depth);

if (! areEquals (actual, MyIntSET.fromString(expected))) {

StdOut.format ("Failed removeBelowDepth(%d) ", depth);

show (MyIntSET.fromString(tree), "original");

show (actual, "actual");

show (MyIntSET.fromString(expected), "expected");

}

}

private static void testRemoveSingles (String expected, String tree) {

MyIntSET actual = MyIntSET.fromString(tree);

actual.removeSingles ();

if (! areEquals (actual, MyIntSET.fromString(expected))) {

StdOut.format ("Failed removeSingles ");

show (MyIntSET.fromString(tree), "original");

show (actual, "actual");

show (MyIntSET.fromString(expected), "expected");

}

}

private static void testRemoveLeaves(String expected, String tree) {

MyIntSET actual = MyIntSET.fromString(tree);

actual.removeLeaves();

if (! areEquals (actual, MyIntSET.fromString(expected))) {

StdOut.format ("Failed removeLeaves ");

show (MyIntSET.fromString(tree), "original");

show (actual, "actual");

show (MyIntSET.fromString(expected), "expected");

}

}

private static void testAddZeroToSingles(String expected, String tree) {

MyIntSET actual = MyIntSET.fromString(tree);

actual.addZeroToSingles ();

if (! expected.equals (actual.toString ())) {

StdOut.format ("Failed addZeroToSingles ");

show (MyIntSET.fromString(tree), "original");

show (actual, "actual");

show (MyIntSET.fromString(expected), "expected");

}

}

/* ***************************************************************************

* Some methods to create and display trees

* DO NOT MODIFY THESE METHODS

*****************************************************************************/

// Add one element to a tree, in BST order

public void put(int key) { root = put(root, key); }

private static Node put(Node n, int key) {

if (n == null) return new Node(key);

if (key < n.key) n.left = put(n.left, key);

else if (key > n.key) n.right = put(n.right, key);

return n;

}

// Test for equality

public static boolean areEquals (MyIntSET a, MyIntSET b) { return areEquals(a.root, b.root); }

private static boolean areEquals (Node x, Node y) {

if (x == null) {

return (y == null);

} else {

return (y != null) && x.key == y.key && areEquals (x.left, y.left) && areEquals (x.right, y.right);

}

}

// Create a tree from a string

public static MyIntSET fromString (String ints) {

MyIntSET set = new MyIntSET ();

for (String s : ints.split (" "))

try { set.put (Integer.parseInt (s)); } catch (NumberFormatException e) {}

return set;

}

// Return the values of the tree in level order

public Iterable levelOrder() {

Queue keys = new Queue<>();

Queue queue = new Queue<>();

queue.enqueue(root);

while (!queue.isEmpty()) {

Node n = queue.dequeue();

if (n == null) continue;

keys.enqueue(n.key);

queue.enqueue(n.left);

queue.enqueue(n.right);

}

return keys;

}

// String representation of the tree

public String toString() {

StringBuilder sb = new StringBuilder();

for (int key: levelOrder())

sb.append (key + " ");

return sb.toString ();

}

// Graphical representation of the tree

public void toGraphviz(String filename) {

GraphvizBuilder gb = new GraphvizBuilder ();

toGraphviz (gb, null, root);

gb.toFileUndirected (filename, "ordering=\"out\"");

}

private static void toGraphviz (GraphvizBuilder gb, Node parent, Node n) {

if (n == null) { gb.addNullEdge (parent); return; }

gb.addLabeledNode (n, Integer.toString (n.key));

if (parent != null) gb.addEdge (parent, n);

toGraphviz (gb, n, n.left);

toGraphviz (gb, n, n.right);

}

}

// //main to test the code//

// public static void main(String args[])

// {

// Binary tree = new Binary();

// tree.root = new Node(1);

// tree.root.left = new Node(2);

// tree.root.right = new Node(3);

// tree.root.left.left = new Node(4);

// tree.root.left.right = new Node(5);

// System.out.println("The size of binary tree is : "+ tree.size());

// System.out.println("The maxdepth of binary tree is : "+ tree.height());

// System.out.println("The sizeodd of binary tree is : "+ tree.sizeOdd());

// System.out.println("The size at depth is : "+ tree.sizeAtDepth(2,2));

// System.out.println("The size above depth is : "+ tree.sizeAboveDepth(2,2));

// System.out.println("The size below depth is : "+ tree.sizeBelowDepth(2,2));

// System.out.println("Check if tree is isPerfectlyBalancedH : "+ tree.isPerfectlyBalancedH());

// System.out.println("Check if tree is isPerfectlyBalancedS : "+ tree.isPerfectlyBalancedS());

// }

// }