JAVA : Recursively complete the IsSemiBalanced() method using one helper functio
ID: 3876009 • 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
//Recursively complete the IsSemiBalanced() method using one helper function for a binary tree.
public class MyIntSET {
//root node, as a had to call them from main function which is static, i added static identifier in front of some functions and variables
private static Node root;
//stores the final isSemiBalanced value
private static Boolean val;
//Node definition
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 static boolean isSemiBalanced() {
// TODO
// returns false if tree is not initialized
if(root == null)
return false;
if(helperFunctionSize(root) == -1 ){
return false;
} else return true;
}
//recursive function which calculates the if sub trees left and right are semi balanced or not
static int helperFunctionSize(Node node)
{
//stores left and right sizes
int sizeLeft;
int sizeRight;
//just a safety check
if (node == null)
return 0;
// case 1: when both child are not null
if(node.left != null && node.right != null){
sizeLeft = helperFunctionSize(node.left);
sizeRight = helperFunctionSize(node.right);
if(sizeLeft == -1 || sizeRight == -1){
//
return -1;
}
if(sizeRight>=sizeLeft){
if(sizeRight<=sizeLeft*3){
return(helperFunctionSize(node.left) + 1 + helperFunctionSize(node.right));
}
else{
return -1;
}
} else{
if(sizeRight*3>=sizeLeft){
return(helperFunctionSize(node.left) + 1 + helperFunctionSize(node.right));
}
else{
return -1;
}
}
}
//case 2: when both child are are null
else if(node.left == null && node.right == null){
return 1;
}
//case 3: when either left or right is null
else{
return -1;
}
}
public static void main(String args[])
{
//checking for different data
root = new Node(-1);
Node node0 = new Node(0);
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
Node node6 = new Node(6);
Node node7 = new Node(7);
Node node8 = new Node(8);
Node node9 = new Node(9);
root.left = node0;
root.right = node1;
node1.left = node2;
node1.right = node3;
//node3.left = node4;
//node3.right = node5;
//node5.left = node6;
//node5.right = node7;
val = isSemiBalanced();
System.out.println(val);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.