# binary tree complete check

• 11-09-2004
ichijoji
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.
• 11-09-2004
xErath
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??
• 11-09-2004
PJYelton
Your return statement has a logic flaw in it. When you hit a leaf
Code:

` (node->left != NULL && onisbalanced(node->left,level+1,numlevels))`
will evaluate to false, meaning the whole return statement will automatically evaluate to false. This of course will make all previous recursive calls false. Check to see if its a leaf node and return true if its within one of the tree height. THEN do the recursive call.
• 11-12-2004
ichijoji
Quote:

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.
• 11-12-2004
```//.... int fullsz = pow(2,hl+1)-1 //.... int fullsz = pow(2,hl+1)-1```