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:

- The tree is Complete Binary Tree (All nodes) till level (d-1).
- 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 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:**

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; }

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….

great work Kamal Rawat (Y)

vry good…….excellent and easy 🙂

thanks Rohit

gooooood

gooooood

Thanks Pavan

Why do we need code at line #12?