JAVA : Recursively complete the IsPerfectlyBalancedH method using one helper fun
ID: 3876022 • 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
// Assuming that the function isPerfectlyBalancedH() is defined in the class // MyIntSET
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()
{
// call the checkIfBalanced() function to check if the
// tree is balanced
// returns -2 if tree is not balanced
// otherwise returns the height
int ans = checkIfBalanced(root);
// if tree is not balanced
if(ans == -2)
return false;
// if tree is balanced
else
return true;
}
// function to check if the tree is balanced
// returns -2 if tree is not balanced
// otherwise returns the height
public int checkIfBalanced(Node x)
{
// if the current node is empty
if(node == null)
return 0;
// if the current node is the leaf node
else if(node.left == null && node.right == null)
return 1;
// if the current node has both child
else if(node.left != null && node.right != null)
{
// recursively check if the left subtree is balanced
int left = checkIfBalanced(node.left);
// recursively check if the right subtree is balanced
int right = checkIfBalanced(node.right);
// if either one of the subtrees is unbalanced
if(left == -2 || right == -2)
return -2;
// if the height of left and right subtree is
// not same
else if(left != right)
return -2;
// if the height of left and right subtree is same
else
return left + 1;
}
// if the current node has only one child
// it is not balanced as the height of left and right
// child is not same
else
return -2;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.