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

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.

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.

How are you defining the height of a tree. If you use the following logic-- if there is a single node in the tree the tree has height zero. If there is 2 or three nodes in the tree then it has height 1. If there are 4 to seven nodes in the tree then it has height 2--then pow(2, (height + 1)) - 1 gives the number of possible nodes in the balanced binary tree. Alternatively, if a tree with one node has height 1, and a tree with 2 or 3 nodes has height 2, and a tree with 4 to 7 nodes has height 3, then pow(2, height) - 1 gives the number of possible nodes in the balanced binary tree.

Quote:

---

Originally Posted by ichijoji

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.

---

Bah!! SIntax ERROR!!!

Code:

---

//....
int fullsz = pow(2,hl+1)-1
//....
int fullsz = pow(2,hl+1)-1

---

Note: e.g. a tree with height 3 has 1+2+4+8 nodes, or 2^(3+1)-1. Recall geometric progressions??