Sep 262012
 

Given a pointer to the root node of the tree, write code to find if it is an Almost Complete Binary Tree or not?

A Binary Tree of depth d is Almost Complete iff:

  1. The tree is Complete Binary Tree (All nodes) till level (d-1).
  2. At level d, (i.e the last level), if a Node is present, then all the Nodes to the left of that node should also be present.

For example, the left tree below is NOT an Almost Complete Binary Tree but the right tree is an Almost Complete Binary Tree

    NOT Almost Complete           Almost Complete Binary Tree
   --------------------           ---------------------------
          _ A _           |             _ A _
        /       \         |           /       \
       B         C        |          B         C
     /   \     /   \      |        /   \     /   \
    D     E    F    G     |       D     E    F    G
   / \        / \         |      / \ 
  H   I      J   K        |     H   I

The left tree is not almost complete because in the last level, the nodes left to Node-J are missing (children of Node-E).

Solution:

The problem may look complex but the solution is simple. For this we will use Level-wise traversal of the Tree.

Traverse the tree in level-wise order and check for below two conditions:
– When first leaf node is found, then all the nodes following it should also be leaf nodes.
– If a Node has right child, then it should also have a Left child.

The 2nd condition is required for cases like below one

      A
       \
        B

Algorithm:

Traverse Nodes of the tree in level-wise order. For each node do the following:
  1. If Node is leaf Node
       leafNodeFound = true
  2. Else IF leafNodeFound AND Node is NOT leaf
       return FALSE;
  3. ELSE IF Node has Right child but not left child
       return FALSE;
return TRUE;

Code:

    bool checkAlmostComplete(root r)
    {
        // Enqueue the root in the Queue.
        Q.enqueue(r);

        bool leafFound = false;
        while(!Q.empty())
        {
            // Print the top element in the Queue and insert its children
            Node *temp = Q.dequeue();

            if( (leafFound == true) && (temp->left != NULL || temp->right == NULL) )
                return true;

            if(temp->left == NULL && temp->right == NULL)
                leafFound = true;

            if(temp->left == NULL && temp->right != NULL)
                return false;

            if(temp->left)
                Q.enqueue(temp->left); 

            if(temp->right)
                Q.enqueue(temp-> right); 
        }
        return true;
    }

 

 

  8 Responses to “Check if a Tree is Almost Complete Binary Tree”

Comments (8)
  1. Hello sir ,
    can you give me the exact definition of complete binary tree and almost complete binary tree with one simple example graph.. I have searched many sites and i got something like this
    Almost complete tree” is a specific case of “complete tree
    Almost complete binary tree is also complete binary tree.
    please clarify my doubt..

    http://stackoverflow.com/questions/26327125/difference-between-complete-and-almost-complete-binary-tree

    And thank you for your previous articles….

  2. great work Kamal Rawat (Y)

  3. vry good…….excellent and easy 🙂

  4. Why do we need code at line #12?

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)