/ Complete the four exercises below. For each \"EXERCISE\" comment, add code imm
ID: 3886884 • Letter: #
Question
/ Complete the four exercises below. For each "EXERCISE" comment, add code immediately below the comment.
//You MUST NOT edit the IDEA/SBT configuration/tests. Altering it in your submission will result in 0 points for this assignment.
//
// This class represents operations on simple Binary Search Trees (BST) with integer keys and no values, i.e., a set of integers.
//
// DO NOT change the name or type of any function (the first line of the function)
// All of the methods in this class are static (and mostly recursive).
// These methods could naturally appear inside Node.java also.
//
// This code is not representative of the object-oriented style of programming, but is concise and allows null to be used to represent leaf nodes.
//////////////////////////////////////////////////////////////////////////////////////
// EXERCISE 1: A tree is size-perfect if for every node, size of left == size of
right.
public boolean isPerfectlyBalancedS () {
// TODO: Complete this method.
return false;
}
//////////////////////////////////////////////////////////////////////////////////////
// EXERCISE 2: A tree is height-perfect if for every node, height of left == height
of right.
public boolean isPerfectlyBalancedH () {
// TODO: Complete this method.
return false;
}
//////////////////////////////////////////////////////////////////////////////////////
// EXERCISE 3: A 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)
public boolean isSemiBalanced (){
// TODO: Complete this method.
return false;
}
//////////////////////////////////////////////////////////////////////////////////////
// EXERCISE 4:
// 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 this method.
return false;
}
Explanation / Answer
int height(Node node)
{
/* base case tree is empty */
if (node == null)
return 0;
/* If tree is not empty then height = 1 + max of left
height and right heights */
return 1 + Math.max(height(node.left), height(node.right));
}
// EXERCISE 1:
public boolean isPerfectlyBalancedS () {
}
//EXERCISE 2:
public boolean isPerfectlyBalancedH (Node node) {
int lh; /* for height of left subtree */
int rh; /* for height of right subtree */
/* If tree is empty then return true */
if (node == null)
return true;
/* Get the height of left and right sub trees */
lh = height(node.left);
rh = height(node.right);
if (Math.abs(lh - rh) <= 1
&& isBalanced(node.left)
&& isBalanced(node.right))
return true;
/* If we reach here then tree is not height-balanced */
return false;
}
//EXERCISE 3:
public boolean isSemiBalanced (Node t) {
}
//EXERCISE 4:
public boolean isOddBalanced() {
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.