Check whether a given Binary Tree is Complete or not

Introduction 

This article will discuss the problem of whether a binary tree is complete or not; before reading the problem statement, let's first discuss in brief what is a complete binary tree.

A complete binary tree is a binary tree in which every level, except the last one, is completely filled, and all nodes are leftmost as possible. 

Let us see the below examples for better understanding:

A complete binary tree

An incomplete binary tree

 

Problem Statement

We are given a Binary Tree. Write a program to check whether the given Binary Tree is a Complete Binary Tree or not.

Sample Examples

Input 1:

      1
    /    \
   2      3
  /  \    /
 4    5  6 

 

Output 1:

 True

 

Explanation: Since every level, except possibly the last, is completely filled, and all nodes are as far left as possible, so the given tree is complete.

Input 2:

      1
    /    \
   2      3
         /  \
        4    5

 

Output 2:  

False

 

Explanation: Since all nodes are not as far left as possible, so the given tree is not complete.

Level order traversal approach

We can use the modified level order traversal to check whether a given binary tree is complete or not. To understand the approach, let us first understand the term ‘Full Node’. ‘Full Node’ is a node if both left and right children are not empty (or not NULL). 

The idea is to do a level order traversal starting from the root. If a node is NOT a full node, then all the remaining nodes in the queue should not have any children.

Also, we need to check one more thing to handle the below case: If a node has a left empty child, then the right child must be empty.   

Algorithm

1. Create an empty queue and enqueue the root node.
2. Use a flag variable of boolean type to mark the end of full nodes.
3. Loop till the queue is empty.
4. Dequeue front node.
5. If we encounter a non-full node before and the current node is not a leaf then a tree cannot be complete. So, return false.
6. If the left child is empty but the right child exists then also a tree cannot be complete. Return false.
7. If the left child exists, enqueue it else if the current node is a non-full node, set the flag to true.
8. If the right child exists, enqueue it else if the current node is a non-full node, set the flag to true.
9. End the loop.

Code In Java

import java.util.LinkedList;
import java.util.Queue;

public class CompleteBTree
{
	static class Node
	{
		int data;
		Node left;
		Node right;
		
		// Constructor
		Node(int d)
		{
			data = d;
			left = null;
			right = null;
		}
	}

	static boolean isCompleteBT(Node root)
	{
		// Base Case
		if(root == null)
			return true;
		
		// Create an empty queue
		Queue<Node> queue =new LinkedList<>();
		
		boolean flag = false;
		
		queue.add(root);
		while(!queue.isEmpty())
		{
			Node temp_node = queue.remove();
			
			/* Check if left child is present*/
			if(temp_node.left != null)
			{
					if(flag == true)
					return false;
				
				// Enqueue Left Child
				queue.add(temp_node.left);
			}
			// If this a non-full node, set the flag as true
			else
				flag = true;
			
			/* Check if right child is present*/
			if(temp_node.right != null)
			{
				if(flag == true)
					return false;
				
				// Enqueue Right Child
				queue.add(temp_node.right);
				
			}
			// If this a non-full node, set the flag as true
			else
				flag = true;
		}
		// If we reach here, then the tree is complete Binary Tree
		return true;
	}

	public static void main(String[] args)
	{
	 Node data = new Node(1);
        data.left = new Node(2);
        data.right = new Node(3);
        data.left.left = new Node(4);
        data.left.right = new Node(5);
        data.right.left = new Node(6);
        data.right.right = new Node(7);
		
		if(isCompleteBT(data) == true)
			System.out.println("Complete Binary Tree");
		else
			System.out.println("NOT Complete Binary Tree");
	}

}

 

Output: 

Complete binary tree

 

Code In C++

#include <iostream>
#include <list>
using namespace std;
 
struct Node
{
    int key;
    Node *left, *right;
 
    Node(int key)
    {
        this->key = key;
        this->left = this->right = nullptr;
    }
};
 
bool isComplete(Node* root)
{
      if (root == nullptr) {
        return true;
    }
 
    list<Node*> queue;
    queue.push_back(root);
 
    Node* front = nullptr;
 
    bool flag = false;
    while (queue.size())
    {
        // dequeue front node
        front = queue.front();
        queue.pop_front();
 
        // if we have encountered a non-full node before and the current   //node is not a leaf, a tree cannot be complete
        if (flag && (front->left || front->right)) {
            return false;
        }
 
        // if the left child is empty and the right child exists,
        // a tree cannot be complete
        if (front->left == nullptr && front->right) {
            return false;
        }
 
        // if the left child exists, enqueue it
        if (front->left) {
            queue.push_back(front->left);
        }
        // if the current node is a non-full node, set the flag to true
        else {
            flag = true;
        }
 
 
        // if the right child exists, enqueue it
        if (front->right) {
            queue.push_back(front->right);
        }
        // if the current node is a non-full node, set the flag to true
        else {
            flag = true;
        }
    }
 
    return true;
}
 
int main()
{         
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
 
    if (isComplete(root)) {
        cout << "Complete binary tree";
    }
    else {
        cout << "Not a complete binary tree";
    }
 
    return 0;
}

 

Output: 

Complete binary tree

Complexity Analysis

Time complexity: O(n); where n is the number of nodes in the Binary Tree.

Space Complexity: O(n) due to the usage of the queue.

Another Approach

A more simple approach would be to check if the NULL Node encountered is the last node of the Binary Tree. If the null node encountered in the binary tree is the last node then it is a complete binary tree and if there exists a valid node even after encountering a null node then the tree is not a complete binary tree.

Algorithm

1. Create an empty queue.
2. Create a flag variable which will be set true when a non full node is seen.
3. Traverse until queue is empty.
4. If we have seen a NULL node, we set the flag to true; else If that NULL node is not the last node then return false.
5. Push both nodes into queue even if there are null.
6. End the loop.

Code In Java

import java.util.*;

class Ninjas{

static class node
{
	int data;
	node left;
	node right;
};

static boolean isCompleteBT(node root)
{

	// Base Case
	if (root == null)
		return true;

	Queue<node > q = new LinkedList<>();
	q.add(root);

	boolean flag = false;

	// Do level order traversal using queue.
	while(!q.isEmpty())
	{
		node temp =q.peek();
		q.remove();

		if(temp == null)
		{
		
		// If we have seen a null node, we set the flag to true
			flag = true ;
		}
	      else
	      {
		// If that null node is not the last node then return false
			if(flag == true)
			{
				return false ;
			}
		
			// Push both nodes even if there are null
			q.add(temp.left) ;		
			q.add(temp.right) ;
		}
	}
	return true;
}

static node newNode(int data)
{
	node node = new node();
	node.data = data;
	node.left = null;
	node.right = null;
	return(node);
}

public static void main(String[] args)
{
	node root = newNode(1);
	root.left = newNode(2);
	root.right = newNode(3);
	root.left.left = newNode(4);
	root.left.right = newNode(5);
	root.right.left = newNode(6);

	if ( isCompleteBT(root) == true )
		System.out.print("Complete Binary Tree");
	else
		System.out.print("NOT Complete Binary Tree");

}
}

 

Output: 

Complete Binary Tree

Code In C++

#include <bits/stdc++.h>
using namespace std;

struct node
{
	int data;
	struct node* left;
	struct node* right;
};

bool isCompleteBT(node* root)
{
	// Base Case
	if (root == NULL)
		return true;

	// Create an empty queue
	queue<node *> q;
	q.push(root);
	bool flag = false;

	// Do level order traversal using queue.
	while(!q.empty())
	{
		node *temp =q.front();
		q.pop();

		if(temp == NULL){
		// If we have seen a NULL node, we set the flag to true
			flag = true ;
		}else
                {
		// If that NULL node is not the last node then return false
			if(flag == true){
				return false ;
			}
			// Push both nodes even if there are null
			q.push(temp->left) ;		
			q.push(temp->right) ;
		}
	}
	return true;
}

struct node* newNode(int data)
{
	struct node* node = (struct node*)malloc(sizeof(struct node));
	node->data = data;
	node->left = NULL;
	node->right = NULL;
	return(node);
}

/* Driver code*/
int main()
{
	struct node *root = newNode(1);
	root->left = newNode(2);
	root->right = newNode(3);
	root->left->left = newNode(4);
	root->left->right = newNode(5);
	root->right->left = newNode(6);

	if ( isCompleteBT(root) == true )
		cout << "Complete Binary Tree";
	else
		cout << "NOT Complete Binary Tree";

	return 0;
}

 

Output: 

Complete Binary Tree

Complexity Analysis

Time complexity: O(n); where n is the number of nodes in the Binary Tree because of traversing each node once.

Space Complexity: O(n) due to the usage of the queue.

Frequently Asked Questions

What are the main characteristics of a Binary Search Tree?

The 2 important features of a binary search tree (BST) are: Each node can have a maximum of two children. For each node, the values of its left child node(if present) must be less than the current node's value. Similarly, the value of the current node must be smaller than the value of its right child node(if any).

What does time complexity mean?

The time complexity in computer science is the computational complexity that describes how long it takes a computer to run an algorithm. Choosing the most efficient algorithm is always better when a fundamental problem can be solved using multiple methods.

What are the limitations of the Binary search algorithm?

The limitations of the Binary Search Algorithm are: It uses a recursive approach which requires more stack space. Programming binary search algorithm is difficult and error-prone. The interaction of this algorithm with memory hierarchy (caching) is poor.

List some types of binary trees.

Some types of Binary trees are Full Binary Trees, Perfect Binary Trees, Complete Binary Trees, Degenerate or Pathological Trees, Skewed Binary trees, and Balanced Binary Trees.

Conclusion

This article discussed the solution for verifying if the given binary tree is complete or not, along with its different approaches, pseudocode, implementation, and code in both JAVA and C++.

Refer to our Guided Path on CodeStudio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, Machine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on CodeStudio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!