# Interview Questions

# Check if a Tree is Almost Complete Binary Tree

- September 9, 2017
- Posted by: Kamal Rawat
- Category: Algorithms

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

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

Hi, these two terms are defined differently by few authors. One set of definitions are given in the below link

http://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html

But I prefer to use the term “Complete binary tree” to mean what is defined as “Full binary tree” in this link, and “Almost complete binary tree” to mean what is defined as “Complete Binary tree” there.

These topics are discussed in detail in our book, “Searching and Sorting for Coding Interviews”.

great work Kamal Rawat (Y)

vry good…….excellent and easy 🙂

thanks Rohit

gooooood

gooooood

Thanks Pavan

Why do we need code at line #12?

Have updated the code.