Check if a binary tree is height balanced

[btoohey4]

Is anyone able to tell me why this doesn't work as a recursive function to find whether a binary tree is height balanced using non-tail recursion? I was provided with everything except the final if statement, so everything else cannot be altered.

template<class T>
int BST<T>::is_perfectly_balanced(BSTNode<T> *p) const
{
  if (p == 0) {
    return 0;
  }
  else {
    int left = is_perfectly_balanced(p->left);
    int right = is_perfectly_balanced(p->right);

    if(abs(left-right) <= 1)
      return 0;
    return -1;
  }
}

This is the output I receive, the proper answer is in the brackets and below is the answer my program outputs.

Empty tree is height balanced? (Yes)
Yes.
Single node is height balanced? (Yes)
Yes.
Linked list of two nodes is height balanced? (Yes)
Yes.
Linked list of three nodes is height balanced? (No)
Yes.
Full binary tree of three nodes (plus one node) is height balanced? (Yes)
Yes.
Full binary tree of three nodes (plus two nodes) is height balanced? (No)
Yes.

Any help would be appreciated, thanks!

[Peter87]

What is the meaning of the number that is_perfectly_balanced returns?

[btoohey4]

@Peter87 Zero or above means true and will result in a 'Yes', otherwise it will be a 'No'.
My driver contains:

bool is_perfectly_balanced() const { return is_perfectly_balanced(root) >= 0; }

The main then calls each check like this:

cout << "Empty tree is height balanced? (Yes)" << endl;
	if (a.is_perfectly_balanced() == true)
		cout << "Yes." << endl;
	else
		cout << "No." << endl;

[Peter87]

Looks like this if statement will always return 0.

if(abs(left-right) <= 1)
      return 0;

The greatest value abs(left-right) can have is if left is 0 and right is -1 but that only gives 1.

[btoohey4]

@Peter87 I understand what you mean but I'm not sure how to fix that without being able to change the code I was given. I know other conditions must be added to the if statement, but everything I try doesn't give the desired output.

[Peter87]

Instead of trying everything, think what will work and then try that. I don't see any logic in the current condition so I suspect a good start is to get rid of it before adding anything more.

[btoohey4]

@Peter87 This is all that google is giving me for it so there has to be some kind of logic behind it. Clearly I've tried to think of what would work..