Thread: binary tree complete check

Ok, I'm working on a binary tree class that needs to have a member function that determines if the tree is complete. The tree is complete if it's balanced and all the nodes on the bottom level are on the left. The tree is balanced if the bottom nodes are no more than one level away from each other. I made this to check if the tree is balanced:

Code:

bool tree_t::isbalanced() {
  if (root == NULL)
    return true;
  else
    return onisbalanced(root,1,getnumlevels());
}
 
bool tree_t::onisbalanced(node_t* node, int level, int numlevels) {
  return (node->left != NULL &&
         onisbalanced(node->left,level+1,numlevels)) &&
         (node->right != NULL &&
         onisbalanced(node->right,level+1,numlevels)) &&
         !(node->left == NULL &&
         node->right == NULL && level < numlevels - 1);
}

This runs through all the nodes recursively and checks that only nodes at the bottom two levels can have no children. This seems like it should work fine to me, but it always says that the tree is unbalanced. I get the feeling there's a really simple way to do this that I'm missing, or maybe I just have some basic logic flaw.

Well this isn't a trivial task so 1st think well on the problem. i've already been assigned once to write a function to verify if a tree is complete but i did do it then. But after thinking about the problem is easy.
You only need to go through the node that go the botom most where the diference in heigth occurs.
Consider these trees

Code:

       o                o        
     /   \            /   \      
   o       o        o       o    
  / \     / \      / \     / \   
 o   o   o   o    o   o   o   o  
/ \ / \ /        / \ /  
o o o o o        o o o

You start by looking at the root node. What you do in a node is the same for all. In a node you look to the left one and then to the right, and check both height for those nodes.
1# If the height from the left one isn't the same or only one unit larger than the height from the right side, then the tree isn't complete.
2.1# If the height matches (case 1) the left node should contain a sub tree with all nodes*, and the control passes to the right node to check if that one is complete
2.2# If the height is diferent (case2) then the right sub tree must contain all nodes, and the control passes to the left node
3# the testing ends when both children are null ( to simplify )

*-> I mean a tree with all nodes when it has 2^(height+1)-1 nodes, or if all levels are all fill.

Now using this logic where a example of iterations on the 2nd tree:

Code:

       o                                            
     /   \                                          
   o       o     control goes     o    control goes 
  / \     / \    left node       / \   to right node
 o   o   o   o                  o   o               
/ \ /                          / \ /                
o o o                          o o o                



                                                     
                                                    
                 control goes      
                 left node         
     o                         
    /                          
    o                          o

So now in pesudo-code

Code:

iscomplete
	check nulls for left and rght
	get heights
	compare heights: is they're valid

	get sizes
	if left.height == right.height
		check size for left subtree
		return right.iscomplete
	else if left.height == right.height-1
		check size for left subtree
		return right.iscomplete
	//the end

And finally in C++

Code:

bool Node::isComplete(){
	if(!left && !right)
		return true;

	int hl = left?left->heigth():-1;
	int hr = right?right->heigth():-1;

	if(hl != hr || hl != hr+1)
		return false;

	int sl = left?left->size():0;
	int sr = right?right->size():0;

	if(hr == hl){//case1
		int fullsz = 2*pow(hl+1)-1
		if( fullsz != sl)
			return false;
		return right->isComplete();
	}else{
		int fullsz = 2*pow(hr+1)-1
		if( fullsz != sr)
			return false;
		return left->isComplete();
	}
}

You're not using templates for the data??

Originally Posted by xErath

Code:

		int fullsz = 2*pow(hl+1)-1

Code:

		int fullsz = 2*pow(hr+1)-1

I'm a little confused about exactly what you mean by this. I thought the formula for the maximum size of a tree was 2*height - 1, but I put that in here and it doesn't work. I also tried pow(2,h_+1) and pow(h_+1,2), and those both produce bogus results too.