JAVA : Recursively complete the IsPerfectlyBalancedH method using one helper fun
ID: 3876007 • Letter: J
Question
JAVA : Recursively complete the IsPerfectlyBalancedH 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 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() {
return 0;}
Explanation / Answer
SOLUTION :
I have written the boolean function to determine if the tree is perfectly balanced or not i.e. return true if the tree is balanced perfectly and false when it is not.
The function isBalanced() returns the desired output by you.
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;
this.left = this.right = null;}
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));
}
// 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(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) == 0 && isBalanced(node.left) && isBalanced(node.right))
return true;
return false;
}
public int isBalanced() { //this function will return height and -2 in case of perfect tree or not
if(isPerfectlyBalancedH(this.root))
return height(this.root);
else
return -2;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.