How to check if a binary tree is a complete binary tree

[swissknife007]

Can please someone give and explain the algorithm and logic of checking if a given tree is a complete binary tree.
Fields available for a node are left and right child and info.
Thanks.

[Narue]

There are multiple ways of doing it, but in my opinion the most instructive is with a level order traversal, since checking for a complete binary tree is a pretty specific operation. By generalizing the problem a bit, you can get more out of the exercise. So here's an updated problem for you:

Q: Given a binary tree of the following definition:

struct node {
    int data;
    struct node *left;
    struct node *right;
};

Write a function that will perform a level order traversal and convert the tree into an array using heap indexing rules. Heap indexing rules state that for each node (numbered 0 to N in level order) the left child is at index 2 * i + 1 and the right child is at 2 * i + 2 .

As an example, given the following degenerate binary tree:

1
        -                      2
   -         -             -        3
 -   -     -   -         -   -    -   4
- - - -   - - - -       - -  - - - - - 5

The array you are to return might look like this:

1-2---3-------4---------------5

Once you have this array, determine if it represents a complete binary tree by testing for null nodes in between non-null nodes. A complete binary tree will have all non-null nodes strictly adjacent to each other. For example, here is a complete binary tree and the array representation:

5
  2         7
1   3     6   -

527136-

Note: The size of the array should be determined as the maximum number of nodes for a tree of height h.

To give you a push in the right direction, you need to figure out how to determine the height of a tree, how to calculate the maximum number of nodes in a tree of given height, and how to perform a level order traversal. Inside the level order traversal you need to maintain the level order index of each node to correctly calculate child indices.

This problem is carefully worded so that you have no choice but to do research on the various techniques, so consult Google before shooting back with questions. I wrote a small program (less than 200 lines) that does all of this. Here are runs on the two examples above:

-
                                5
                                        -
                        4
                                -
                3
                        -
        2
                -
1
        -

*-*---*-------*---------------*
Invalid complete tree

-
        7
                        -
                6
                        -
5
                        -
                3
                        -
        2
                        -
                1
                        -

******-
Complete!

Feel free to match that output if you want. A tree dump with a 90 degree rotation is far easier than the usual textbook representation.