Complete the code for the four problems that follow. Leave everything as a publi
ID: 3886947 • Letter: C
Question
Complete the code for the four problems that follow. Leave everything as a public boolean. Possibly relevant code is included here:
Rules:
* - 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
* - no loops
* - 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)
public int size () {
return size (root, 0);
}
private static int size (Node x, int sz) {
if (x != null) {
sz = sz + 1;
sz = size (x.left, sz);
sz = size (x.right, sz);
}
return sz;
}
// the height of the tree
public int height() {
return height(this.root);
}
private int height(Node current) {
if (current == null) {
return -1;
}
else {
return 1+ Math.max(height(current.left), height(current.right));
}
}
THINGS NEEDING SOLVING STARTS HERE:
#1
// 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: complete code
return false;
}
#2
// 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: complete code
return false;
}
#3
// 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: complete code
return false;
}
#4
// 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-child <= size-of-smaller-child * 3)
// hint: in the helper, return -1 if the tree is not semi-perfect, otherwise return the size
public boolean isSemiBalanced() {
// TODO: complete code
return false;
}
Explanation / Answer
public boolean isPerfectlyBalancedS() {
if (isPerfectlyBalanced(root)>=0) return true;
else return false;
}
public int isPerfectlyBalanced(Node x){
if ((x == null )||((x.left==null)&&(x.right==null))) return 0;
if (size(x.left) == size(x.right)){
return size(x.left) + isPerfectlyBalanced(x.left)+ isPerfectlyBalanced(x.right);
}
else return -1;
}
public boolean isPerfectlyBalancedH() {
if (isPerfectlyBalanced(root)==-2) return false;
else if (isPerfectlyBalanced(root)!=-2) return true;
else return true;
}
public int isPerfectlyBalancedH(Node x){
if (!isPerfectlyBalancedS()) return -2;
if(height(x.left)==height(x.right)){
return height(x.left)+ isPerfectlyBalancedH(x.left)+isPerfectlyBalancedH(x.right);
}
else return -2;
}
public boolean isOddBalanced() {
if ( isOddBalanced(root)==-1) return false;
else return true;
}
public int isOddBalanced(Node x){
if (x == null) return -1;
if (sizeOdd(x.left)==sizeOdd(x.right)){
return sizeOdd(x.left)+isOddBalanced(x.left)+isOddBalanced(x.right);
}
else return 0;
}
public boolean isSemiBalanced() {
if (isSemiBalanced(root)==-1) return false;
else if (isSemiBalanced(root) != -1) return true;
return true;
}
public int isSemiBalanced(Node x){
if (x == null )return 0;
int sizeL=-1, sizeR=-2, max, min;
sizeL = size(x.left);
sizeR = size(x.right);
max = Math.max(sizeL, sizeR);
min = Math.min(sizeL, sizeR);
if ((max == min)||(max<=(min*3))) return max;
else return -1;
}