Check if a Binary Tree is Complete Binary Tree

A Complete Binary Tree is a Binary Tree where each level is completely filled. For example, all the trees below are complete Binary trees

Height=1    Height=2      Height=3
--------    --------      --------
   A          A              A
             / \           /   \
            B   C         B     C
                         / \   / \
                        D  E  F   G

And the trees below are not Complete (because there are holes in between):

   A           A              A
  /           / \           /   \
 B           B   C         B     C
              \           / \   /
               D         D  E  F

Given a binary tree, write code to check if the tree is a Complete Binary Tree or not.

Wrong Solution-1: Strictly Binary tree is not complete Binary tree

If each node has either 2 or zero child then its a Complete binary Tree.
No

The below tree is not Complete (it is strict Binary tree, but not Complete).

           A
          / \
         B   C
            / \
           E   D

Wrong-Solution-2: If all leaf nodes are at same level

If all leaf nodes are at the same level then the tree is Complete Binary tree?
NO

The below tree has all the leaf nodes at the same level, but it is still not a complete binary tree

           A   
            \  
             C 
            / \
           E   D

There are only two nodes E and F and both are at same level, but it is not a Complete Binary tree.

Correct Solution-1: Combine above two wrong solutions

If we combine the other two solutions. i.e All the leaf nodes should be at the same level AND all the nodes should have either zero or two childs.

Correct Solution-2: Use equation between height and number of nodes

Fact about Complete binary Tree.

If height of the tree is h, then the total number of nodes will be 2^h-1 and vice-versa.

Hence, If we just find height of the Binary tree, and then count the number of nodes in the tree then we can say for certainty, whether or not the tree is Complete.

Algorithm:

h = Height of Tree
n = Number of nodes in the Tree
if(n = 2^h -1)
    return true
else
    return false

Code:

If the Node of tree is defined as

struct Node
{
    Node *lptr;
    int data;
    Node *rptr;
};

Then below are the functions to compute height and the number of Nodes in Binary tree:

/** Function to compute the height of the tree.
 *  root is a pointer to the root of the tree
 */
int getHeight(Node* root)
{
    if (root == NULL)
       return 0;
    // Compute height of each tree
    int heightLeft = getHeight(root->lptr);
    int heightRight = getHeight(root->rptr);
    /* use the larger one */
    if (heightLeft > heightRight)
        return(heightLeft + 1);
    else
        return(heightRight + 1);
}
/**
 * Count the total number of nodes in a Binary tree.
 */
int countNodes(Node* r)
{
    if(r == NULL)
        return 0;
    return 1 + countNodes(r->rptr) + countNodes(r->lptr);
}

The two functions above can be merged into one, so that the tree is traversed only once. Pass a count parameter as a reference parameter to the getHeight function and increment it once in each recursive function call. The time complexity will still be O(n) but we will gain in the constant factor (In this case the tree is traversed twice – once to compute the height and then to count the number of nodes).

And finally below code check whether the tree is a complete binary tree of not.

// Helper function. to compute x^n. Assumes n to be positive.
int exponent(int x, int n)
{
    int pow = 1;
    int i=0;
    for(i=0; i<n; i++)
         pow *= x;
    return pow;
}
/**
 * returns true if a binary tree is complete binary tree, false otherwise
 */
int checkCompleteTree(Node* r)
{
    if(r == NULL)
        return true;
    int h = getHeight(r);
    int n = countNodes(r);
    if(n == exponent(2,h)-1)
        return 1;
    else
        return 0;
}

The time complexity of above function is O(n).. Both getHeight and countNodes functions takes O(n) time each.