Check if a Tree is Almost Complete Binary Tree

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 an Almost complete because in the last level, the nodes left to Node-J are missing (children of Node-E).

Solution-1: Use level order traversal.

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 2^nd 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:

// TREE NODE
struct Node
{
    int data;
    Node* left;
    Node* right;
    Node(int v):data(v), left(NULL), right(NULL){}
};
class Queue
{
    struct QNode{
        Node *data;
        QNode *next;
        QNode(Node* v): data(v),next(NULL){}
    }* head, *tail;
public:
    Queue(): head(NULL), tail(NULL){}
    void enqueue(Node *x){
        if(tail == NULL)
            head = tail = new QNode(x);
        else
        {
            tail->next = new QNode(x);
            tail = tail->next;
        }
    }
    Node* dequeue()
    {
        if(head == NULL)
        {
            return NULL;
        }
        Node* x = head->data;
        QNode *temp = head;
        head = head->next;
        delete temp;
        if(head == NULL){ tail = NULL; }
        return x;
    }
    bool empty()
    {
        return (head == NULL);
    }
};
// All nodes after the first leaf are also leaf nodes.
// If a node is has not-null left child, then its right child should also be null
bool checkAlmostComplete(Node* r)
{
    Queue Q;
    // 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();
        // FOUND LEAF AND CURRENT NODE IS NOT LEAF
        if( (leafFound == true) && (temp->left != NULL || temp->right != NULL) )
            return false;
        // NODE HAS ONLY RIGHT CHILD
        if(temp->left == NULL && temp->right != NULL)
            return false;
        // FOUND FIRST LEAF NODE
        if(temp->left == NULL && temp->right ==NULL && leafFound == false)
            leafFound = true;
        if(temp->left)
            Q.enqueue(temp->left);
        if(temp->right)
            Q.enqueue(temp-> right);
    }
    return true;
}

This code takes O(n) time and O(n) extra memory for queue.