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??