QWERTY
QWERTY

Reputation: 25

How to check if a Binary Search Tree is Perfectly Balanced?

I have this homework problem and I have completed all methods except this one, isPerfectlyBalanced().

All my tests pass except one that should return false but instead returns true. I have attached my current code and the test that is failing. Any description on how to go about this or even let me know where my code is wrong is appreciated!

private boolean isPerfectlyBalanced(Node node) {

    if (node == null) {
        return true;
    }

    if(size(node.left) == size(node.right)) {
        return true;
    }
    isPerfectlyBalanced(node.left);
    isPerfectlyBalanced(node.right);
    return false;

}


public boolean isPerfectlyBalancedS() {
    // TODO
    if (root == null) {
        return true;
    }
    return isPerfectlyBalanced(root);

}

Here is my test that is failing:

assertFalse(set.isPerfectlyBalancedS());

Thank you!

My size method:

private int size(Node node){
    if (node == null){
        return 0;
    } else {
        return (size(node.left) + 1 + size(node.right));
    }
}
public int size() {
    // TODO
    return size(root);
}

Upvotes: 0

Views: 342

Answers (1)

NeplatnyUdaj
NeplatnyUdaj

Reputation: 6242

On the last line of the first method, you probably want to do this:

return (isPerfectlyBalanced(node.left) && isPerfectlyBalanced(node.right));

instead of

isPerfectlyBalanced(node.left);
isPerfectlyBalanced(node.right);
return false;

In your code, you dismiss the result of the isPerfectlyBalanced on the subtrees and always return false.

Upvotes: 5

Related Questions