Question

[btech]

I want to check to see if a binary tree is perfect. this means that the height of the left and right subtrees of the root are equal and the left and right subtrees of the root are perfectly balanced binary trees. I have written the function but am not sure it is correct. can someone please check my algorithm?

template<class elemType>
int check(AVLNode<elemType>* &root) 
{
        int height = 0;
        int lh = 0;
        int rh = 0;
        if (node == null) {
            return height;
        }
        if (root->llink != null) {
            lh = check(root->llink);
        }
        if (root->rlink != null) {
            rh = check(root->rlink);
        }
        if (root->bfactor != (rh - lh)) {
            return 0;
        }
        if (lh > height) height = lh;
        if (rh > height) height = rh;
        return ++height;
    }

[Salem]

Why don't you write some test programs for yourself to create trees with varying degrees of unbalance to test the function.

[btech]

Why don't you write some test programs for yourself to create trees with varying degrees of unbalance to test the function.

I have tried but keep receiving errors

#include <iostream>
#include "avlTree.h"

using namespace std;

int main()
{
	AVLNode<int> avlTree;

	int num;

	cout << "Enter integers ending with -999" << endl;

	cin >> num;
	while(num != -999)
	{
		cin>>num;
	}
            cout << avlTree.check();

	return 0;
}

[Salem]

> I have tried but keep receiving errors
Of course, not posting the errors goes a long way :rolleyes:

You merely declare a tree and then read in some numbers. How about actually inserting those numbers into the tree before calling check()?

Do you even have a constructor for your tree to make it properly empty before trying to check() it? Is it for example just barfing on junk data?

Being able to write test code and debug your own code is a primary skill, so you may as well get some practice in.