JAVA : Recursively complete the IsSemiBalanced() method using one helper functio
ID: 3877473 • Letter: J
Question
JAVA : Recursively complete the IsSemiBalanced() method using one helper function for a binary tree.
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; }
}
// 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
return false;
}
Explanation / Answer
The following recursive semi balanced method :
public static boolean isSemiBalanced (Node t) {
int n = isSemiBalancedInt(t);
if (n <= -1) return false;
return true;
}
private static int isSemiBalancedInt(Node node) {
if (node == null) return 1;
if (node.left == null && node.right == null) return 0;
else if (node.left == null || node.right == null) return -1;
else {
int Maxsize = Math.max(isSemiBalancedInt(node.left), isSemiBalancedInt(node.right));
int Minsize = Math.min(isSemiBalancedInt(node.left), isSemiBalancedInt(node.right));
if (Maxsize == -1 || Minsize == -1) return -1;
if (Maxsize <= 3 * Minsize) return isSemiBalancedInt(node.left) + isSemiBalancedInt(node.right);
}
return -1;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.