Check whether a given Binary Tree is Complete or not | Set 1 (Iterative Solution)

Last Updated : 14 Jul, 2023

Given a Binary Tree, write a function to check whether the given Binary Tree is Complete Binary Tree or not.
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. See the following examples.

The following trees are examples of Complete Binary Trees
    1
  /   \
 2     3
  
       1
    /    \
   2       3
  /
 4
       1
    /    \
   2      3
  /  \    /
 4    5  6

The following trees are examples of Non-Complete Binary Trees
    1
      \
       3
  
       1
    /    \
   2       3
    \     /  \   
     4   5    6
       1
    /    \
   2      3
         /  \
        4    5

The method 2 of level order traversal post can be easily modified to check whether a tree is Complete or not. To understand the approach, let us first define the term ‘Full Node’. A node is ‘Full Node’ if both left and right children are not empty (or not NULL).

The approach is to do a level order traversal starting from the root. In the traversal, once a node is found which is NOT a Full Node, all the following nodes must be leaf nodes.

Also, one more thing needs to be checked to handle the below case: If a node has an empty left child, then the right child must be empty.

Thanks to Guddu Sharma for suggesting this simple and efficient approach.

C++

// C++ program to check if a given binary tree is complete
// or not
#include <bits/stdc++.h>
using namespace std;
 
// A binary tree node has data, pointer to left child and a
// pointer to right child
struct node {
    int data;
    struct node* left;
    struct node* right;
};
 
// Given a binary tree, return true if the tree is complete
// else false
bool isCompleteBT(node* root)
{
 
    // Create an empty queue
    // int rear, front;
    // node **queue = createQueue(&front, &rear);
    queue<node*> q;
    q.push(root);
    // Create a flag variable which will be set true when a
    // non null node is seen
    bool flag = false;
 
    // Do level order traversal using queue.
    // enQueue(queue, &rear, root);
    while (!q.empty()) {
        node* temp = q.front();
        q.pop();
 
        /* Check if left child is present*/
        if (temp->left) {
            // If we have seen a non full node, and we see a
            // node with non-empty left child, then the
            // given tree is not a complete Binary Tree
            if (flag == true)
                return false;
 
            q.push(temp->left); // Enqueue Left Child
        }
        // If this a non-full node, set the flag as true
        else
            flag = true;
 
        /* Check if right child is present*/
        if (temp->right) {
            // If we have seen a non full node, and we see a
            // node with non-empty right child, then the
            // given tree is not a complete Binary Tree
            if (flag == true)
                return false;
 
            q.push(temp->right); // Enqueue Right Child
        }
        // 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;
}
 
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
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()
{
    /* Let us construct the following Binary Tree which
        is not a complete Binary Tree
              1
            /  \
            2   3
           / \   \
          4   5   6
        */
 
    node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->right = newNode(6);
 
    if (isCompleteBT(root) == true)
        cout << "Complete Binary Tree";
    else
        cout << "NOT Complete Binary Tree";
 
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta
// (kriSania804)

C

// A program to check if a given binary tree is complete or
// not
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX_Q_SIZE 500
 
/* A binary tree node has data, a pointer to left child
   and a pointer to right child */
struct node {
    int data;
    struct node* left;
    struct node* right;
};
 
/* function prototypes for functions needed for Queue data
   structure. A queue is needed for level order traversal */
struct node** createQueue(int*, int*);
void enQueue(struct node**, int*, struct node*);
struct node* deQueue(struct node**, int*);
bool isQueueEmpty(int* front, int* rear);
 
/* Given a binary tree, return true if the tree is complete
   else false */
bool isCompleteBT(struct node* root)
{
    // Base Case: An empty tree is complete Binary Tree
    if (root == NULL)
        return true;
 
    // Create an empty queue
    int rear, front;
    struct node** queue = createQueue(&front, &rear);
 
    // Create a flag variable which will be set true
    // when a non full node is seen
    bool flag = false;
 
    // Do level order traversal using queue.
    enQueue(queue, &rear, root);
    while (!isQueueEmpty(&front, &rear)) {
        struct node* temp_node = deQueue(queue, &front);
 
        /* Check if left child is present*/
        if (temp_node->left) {
            // If we have seen a non full node, and we see a
            // node with non-empty left child, then the
            // given tree is not a complete Binary Tree
            if (flag == true)
                return false;
 
            enQueue(queue, &rear,
                    temp_node->left); // Enqueue Left Child
        }
        else // If this a non-full node, set the flag as
             // true
            flag = true;
 
        /* Check if right child is present*/
        if (temp_node->right) {
            // If we have seen a non full node, and we see a
            // node with non-empty right child, then the
            // given tree is not a complete Binary Tree
            if (flag == true)
                return false;
 
            enQueue(
                queue, &rear,
                temp_node->right); // Enqueue Right Child
        }
        else // If this a non-full node, set the flag as
             // true
            flag = true;
    }
 
    // If we reach here, then the tree is complete Binary
    // Tree
    return true;
}
 
/*UTILITY FUNCTIONS*/
struct node** createQueue(int* front, int* rear)
{
    struct node** queue = (struct node**)malloc(
        sizeof(struct node*) * MAX_Q_SIZE);
 
    *front = *rear = 0;
    return queue;
}
 
void enQueue(struct node** queue, int* rear,
             struct node* new_node)
{
    queue[*rear] = new_node;
    (*rear)++;
}
 
struct node* deQueue(struct node** queue, int* front)
{
    (*front)++;
    return queue[*front - 1];
}
 
bool isQueueEmpty(int* front, int* rear)
{
    return (*rear == *front);
}
 
/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
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 program to test above functions*/
int main()
{
    /* Let us construct the following Binary Tree which
       is not a complete Binary Tree
             1
           /   \
          2     3
         / \     \
        4   5     6
     */
 
    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->right = newNode(6);
 
    if (isCompleteBT(root) == true)
        printf("Complete Binary Tree");
    else
        printf("NOT Complete Binary Tree");
 
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta
// (kriSania804)

Java

// A Java program to check if a given binary tree is
// complete or not
 
import java.util.LinkedList;
import java.util.Queue;
 
public class CompleteBTree {
    /* A binary tree node has data, a pointer to left child
       and a pointer to right child */
    static class Node {
        int data;
        Node left;
        Node right;
 
        // Constructor
        Node(int d)
        {
            data = d;
            left = null;
            right = null;
        }
    }
 
    /* Given a binary tree, return true if the tree is
       complete else false */
    static boolean isCompleteBT(Node root)
    {
        // Base Case: An empty tree is complete Binary Tree
        if (root == null)
            return true;
 
        // Create an empty queue
        Queue<Node> queue = new LinkedList<>();
 
        // Create a flag variable which will be set true
        // when a non full node is seen
        boolean flag = false;
 
        // Do level order traversal using queue.
        queue.add(root);
        while (!queue.isEmpty()) {
            Node temp_node = queue.remove();
 
            /* Check if left child is present*/
            if (temp_node.left != null) {
                // If we have seen a non full node, and we
                // see a node with non-empty left child,
                // then the given tree is not a complete
                // Binary Tree
                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 we have seen a non full node, and we
                // see a node with non-empty right child,
                // then the given tree is not a complete
                // Binary Tree
                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;
    }
 
    /* Driver program to test above functions*/
    public static void main(String[] args)
    {
 
        /* Let us construct the following Binary Tree which
          is not a complete Binary Tree
                1
              /   \
             2     3
            / \     \
           4   5     6
        */
 
        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.right = new Node(6);
 
        if (isCompleteBT(root) == true)
            System.out.println("Complete Binary Tree");
        else
            System.out.println("NOT Complete Binary Tree");
    }
}
// This code is contributed by Sumit Ghosh

Python

# Check whether a binary tree is complete or not
 
# A binary tree node
 
 
class Node:
 
    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Given a binary tree, return true if the tree is complete
# else return false
 
 
def isCompleteBT(root):
 
    # Base Case: An empty tree is complete Binary tree
    if root is None:
        return True
 
    # Create an empty queue
    queue = []
 
    # Create a flag variable which will be set True
    # when a non-full node is seen
    flag = False
 
    # Do level order traversal using queue
    queue.append(root)
    while(len(queue) > 0):
        tempNode = queue.pop(0)  # Dequeue
 
        # Check if left child is present
        if (tempNode.left):
 
            # If we have seen a non-full node, and we see
            # a node with non-empty left child, then the
            # given tree is not a complete binary tree
            if flag == True:
                return False
 
            # Enqueue left child
            queue.append(tempNode.left)
 
            # If this a non-full node, set the flag as true
        else:
            flag = True
 
        # Check if right child is present
        if(tempNode.right):
 
            # If we have seen a non full node, and we
            # see a node with non-empty right child, then
            # the given tree is not a complete BT
            if flag == True:
                return False
 
            # Enqueue right child
            queue.append(tempNode.right)
 
        # If this is non-full node, set the flag as True
        else:
            flag = True
 
    # If we reach here, then the tree is complete BT
    return True
 
 
# Driver program to test above function
 
""" Let us construct the following Binary Tree which
      is not a complete Binary Tree
            1
          /   \
         2     3
        / \     \
       4   5     6
    """
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(6)
 
if (isCompleteBT(root)):
    print "Complete Binary Tree"
else:
    print "NOT Complete Binary Tree"
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// C# program to check if a given
// binary tree is complete or not
using System;
using System.Collections.Generic;
 
public class CompleteBTree {
    /* A binary tree node has data,
    pointer to left child and a
     pointer to right child */
    public class Node {
        public int data;
        public Node left;
        public Node right;
 
        // Constructor
        public Node(int d)
        {
            data = d;
            left = null;
            right = null;
        }
    }
 
    /* Given a binary tree, return
    true if the tree is complete
    else false */
    static bool isCompleteBT(Node root)
    {
        // Base Case: An empty tree
        // is complete Binary Tree
        if (root == null)
            return true;
 
        // Create an empty queue
        Queue<Node> queue = new Queue<Node>();
 
        // Create a flag variable which will be set true
        // when a non full node is seen
        bool flag = false;
 
        // Do level order traversal using queue.
        queue.Enqueue(root);
        while (queue.Count != 0) {
            Node temp_node = queue.Dequeue();
 
            /* Check if left child is present*/
            if (temp_node.left != null) {
                // If we have seen a non full node,
                // and we see a node with non-empty
                // left child, then the given tree is not
                // a complete Binary Tree
                if (flag == true)
                    return false;
 
                // Enqueue Left Child
                queue.Enqueue(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 we have seen a non full node,
                // and we see a node with non-empty
                // right child, then the given tree
                // is not a complete Binary Tree
                if (flag == true)
                    return false;
 
                // Enqueue Right Child
                queue.Enqueue(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;
    }
 
    /* Driver code*/
    public static void Main()
    {
 
        /* Let us construct the following Binary Tree which
        is not a complete Binary Tree
                1
            / \
            2     3
            / \     \
        4 5     6
        */
 
        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.right = new Node(6);
 
        if (isCompleteBT(root) == true)
            Console.WriteLine("Complete Binary Tree");
        else
            Console.WriteLine("NOT Complete Binary Tree");
    }
}
 
/* This code contributed by PrinciRaj1992 */

Javascript

<script>
  
// JavaScript program to check if a given
// binary tree is complete or not
 
/* A binary tree node has data, 
pointer to left child and a
 pointer to right child */
class Node
{
    // Constructor
    constructor(d)
    {
        this.data = d;
        this.left = null;
        this.right = null;
    }
}
 
/* Given a binary tree, return 
true if the tree is complete
else false */
function isCompleteBT(root)
{
    // Base Case: An empty tree 
    // is complete Binary Tree
    if(root == null)
        return true;
     
    // Create an empty queue
    var queue = [];
     
    // Create a flag variable which will be set true
    // when a non full node is seen
    var flag = false;
     
    // Do level order traversal using queue.
    queue.push(root);
    while(queue.length != 0)
    {
        var temp_node = queue.shift();
         
        /* Check if left child is present*/
        if(temp_node.left != null)
        {
            // If we have seen a non full node,
            // and we see a node with non-empty
            // left child, then the given tree is not
            // a complete Binary Tree
            if(flag == true)
                return false;
             
            // push Left Child
            queue.push(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 we have seen a non full node,
            // and we see a node with non-empty
            // right child, then the given tree 
            // is not a complete Binary Tree
            if(flag == true)
                return false;
             
            // push Right Child
            queue.push(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;
}
 
/* Driver code*/
/* Let us construct the following Binary Tree which
is not a complete Binary Tree
        1
    / \
    2     3
    / \     \
4 5     6
*/
var 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.right = new Node(6);
 
if(isCompleteBT(root) == true)
    document.write("Complete Binary Tree");
else
    document.write("NOT Complete Binary Tree");
 
 
</script>

Output

NOT Complete Binary Tree

Time Complexity: O(n) where n is the number of nodes in a given Binary Tree
Auxiliary Space: O(h) where h is the height of the given Binary Tree

Method 2: A more simple approach would be to check whether 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.

C++

// C++ program to check if a given
// binary tree is complete or not
#include <bits/stdc++.h>
using namespace std;
 
// A binary tree node has data, pointer to left child and a
// pointer to right child */
struct node {
    int data;
    struct node* left;
    struct node* right;
};
 
/* Given a binary tree, return true if the tree is complete
 * else false */
bool isCompleteBT(node* root)
{
    
// Create an empty queue
    queue<node*> q;
    q.push(root);
    // Create a flag variable which will be set true
    // when a non null node is seen
    bool flag = false;
 
    // Do level order traversal using queue.
    // enQueue(queue, &rear, root);
    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);
        }
    }
 
    // If we reach here, then the tree is complete Binary
    // Tree
    return true;
}
 
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
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()
{
    /* Let us construct the following Binary Tree which
        is not a complete Binary Tree
             1
            / \
            2   3
           / \   \
          4   5   6
        */
 
    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->right = newNode(6);
 
    if (isCompleteBT(root) == true)
        cout << "Complete Binary Tree";
    else
        cout << "NOT Complete Binary Tree";
 
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta
// (kriSania804)

C

// A program to check if a given binary tree is complete or
// not
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX_Q_SIZE 500
 
/* A binary tree node has data, a pointer to left child
and a pointer to right child */
struct node {
    int data;
    struct node* left;
    struct node* right;
};
 
/* function prototypes for functions needed for Queue data
structure. A queue is needed for level order traversal */
struct node** createQueue(int*, int*);
void enQueue(struct node**, int*, struct node*);
struct node* deQueue(struct node**, int*);
bool isQueueEmpty(int* front, int* rear);
 
/* Given a binary tree, return true if the tree is complete
else false */
bool isCompleteBT(struct node* root)
{
    // Base Case: An empty tree is complete Binary Tree
    if (root == NULL)
        return true;
 
    // Create an empty queue
    int rear, front;
    struct node** queue = createQueue(&front, &rear);
    enQueue(queue, &rear, root);
 
    // Create a flag variable which will be set true
    // when a non full node is seen
    bool flag = false;
 
    // Do level order traversal using queue.
 
    while (!isQueueEmpty(&front, &rear)) {
        struct node* temp_node = deQueue(queue, &front);
 
        if (!temp_node) {
            // 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
            enQueue(queue, &rear,
                    temp_node->left); // Enqueue Left Child
            enQueue(
                queue, &rear,
                temp_node->right); // Enqueue right Child
        }
    }
    return true;
}
 
/*UTILITY FUNCTIONS*/
struct node** createQueue(int* front, int* rear)
{
    struct node** queue = (struct node**)malloc(
        sizeof(struct node*) * MAX_Q_SIZE);
 
    *front = *rear = 0;
    return queue;
}
 
void enQueue(struct node** queue, int* rear,
             struct node* new_node)
{
    queue[*rear] = new_node;
    (*rear)++;
}
 
struct node* deQueue(struct node** queue, int* front)
{
    (*front)++;
    return queue[*front - 1];
}
 
bool isQueueEmpty(int* front, int* rear)
{
    return (*rear == *front);
}
 
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
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 program to test above functions*/
int main()
{
    /* Let us construct the following Binary Tree which
      is not a complete Binary Tree
         1
        / \
       2   3
      / \    \
     4   5     6
      */
 
    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->right = newNode(6);
 
    if (isCompleteBT(root) == true)
        printf("Complete Binary Tree");
    else
        printf("NOT Complete Binary Tree");
 
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta (kriSania804)

Java

// Java program to check if a given
// binary tree is complete or not
import java.util.*;
 
public class GFG{
  
/* A binary tree node has data,
pointer to left child and a
pointer to right child */
static class node
{
    int data;
    node left;
    node right;
};
  
/* Given a binary tree, return
true if the tree is complete
else false */
static boolean isCompleteBT(node root)
{
   
    // Base Case: An empty tree
    // is complete Binary Tree
    if (root == null)
        return true;
  
    // Create an empty queue
    Queue<node > q = new LinkedList<>();
    q.add(root);
   
    // Create a flag variable which will be set true
    // when a non full node is seen
    boolean flag = false;
  
    // Do level order traversal using queue.
    //enQueue(queue, &rear, root);
    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) ;
        }    
    }
  
    // If we reach here, then the
    // tree is complete Binary Tree
    return true;
}
  
/* Helper function that allocates a new node with the
given data and null left and right pointers. */
static node newNode(int data)
{
    node node = new node();
    node.data = data;
    node.left = null;
    node.right = null;
    return(node);
}
  
/* Driver code*/
public static void main(String[] args)
{
    /* Let us construct the following Binary Tree which
        is not a complete Binary Tree
             1
            / \
            2   3
           / \   \
          4   5   6
        */
  
    node root = newNode(1);
    root.left = newNode(2);
    root.right = newNode(3);
    root.left.left = newNode(4);
    root.left.right = newNode(5);
    root.right.right = newNode(6);
  
    if ( isCompleteBT(root) == true )
        System.out.print("Complete Binary Tree");
    else
        System.out.print("NOT Complete Binary Tree");
  
}
}
  
// This code is contributed by Rajput-Ji

Python3

# A binary tree node has data, pointer to left child and a
# pointer to right child
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Given a binary tree, return true if the tree is complete
# else false
def isCompleteBT(root: Node) -> bool:
    # Base Case: An empty tree is complete Binary Tree
    if root is None:
        return True
 
    # Create an empty queue
    q = []
    q.append(root)
    # Create a flag variable which will be set true
    # when a non full node is seen
    flag = False
 
    # Do level order traversal using queue.
    while len(q) != 0:
        temp = q.pop(0)
 
        if temp is None:
            # 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:
                return False
            # Push both nodes even if there are null
            q.append(temp.left)
            q.append(temp.right)
 
    # If we reach here, then the tree is complete Binary
    # Tree
    return True
 
# Helper function that allocates a new node with the
# given data and NULL left and right pointers.
def newNode(data: int) -> Node:
    temp = Node(data)
    return temp
 
# Driver code
if __name__ == '__main__':
    # Let us construct the following Binary Tree which
    # is not a complete Binary Tree
    #        1
    #       / \
    #      2   3
    #     / \   \
    #    4   5   6
    root = newNode(1)
    root.left = newNode(2)
    root.right = newNode(3)
    root.left.left = newNode(4)
    root.left.right = newNode(5)
    root.right.right = newNode(6)
 
    if isCompleteBT(root) == True:
        print("Complete Binary Tree")
    else:
        print("NOT Complete Binary Tree")
 
# This code is contributed by lokeshpotta20.

C#

// C# program to check if a given
// binary tree is complete or not
using System;
using System.Collections.Generic;
 
class GFG
{
 
/* A binary tree node has data,
pointer to left child and a
pointer to right child */
 public class node
{
    public int data;
    public node left;
    public node right;
}
 
/* Given a binary tree, return
true if the tree is complete
else false */
static bool isCompleteBT(node root)
{
 
    // Base Case: An empty tree
    // is complete Binary Tree
    if (root == null)
        return true;
 
    // Create an empty queue
    Queue<node > q = new Queue<node>();
    q.Enqueue(root);
 
    // Create a flag variable which will be set true
    // when a non full node is seen
    bool flag = false;
 
    // Do level order traversal using queue.
    //enQueue(queue, &rear, root);
    while(q.Count!=0)
    {
        node temp =q.Peek();
        q.Dequeue();
 
        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.Enqueue(temp.left) ;        
            q.Enqueue(temp.right) ;
        }
    }
 
    // If we reach here, then the
    // tree is complete Binary Tree
    return true;
}
 
/* Helper function that allocates a new node with the
given data and null left and right pointers. */
public static  node newNode(int data)
{
    node node = new node();
    node.data = data;
    node.left = null;
    node.right = null;
    return(node);
}
 
 
// Driver Code
public static void Main()
{
    /* Let us construct the following Binary Tree which
        is not a complete Binary Tree
             1
            / \
            2 3
           / \ \
           4 5 6
        */
 
    node root = newNode(1);
    root.left = newNode(2);
    root.right = newNode(3);
    root.left.left = newNode(4);
    root.left.right = newNode(5);
    root.right.right = newNode(6);
 
    if ( isCompleteBT(root) == true )
        Console.Write("Complete Binary Tree");
    else
        Console.Write("NOT Complete Binary Tree");
 
}
}
 
// This code is contributed by jana_sayantan.

Javascript

// JavaScript program to check if a given 
// binary tree is complete or not
class node{
    constructor(data){
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
 
// Given a binary tree, return true if the tree is complete 
// else false
function isCompleteBT(root){
    // Base Case: An empty tree is complete Binary tree
    if(root == null) return true;
     
    // create an empty queue
    let q = [];
    q.push(root);
    // Create a flag variable which will be set true
    // when a non full node is seen
    let flag = false;
     
    // Do level order traversal using queue.
    // enQueue(queue, &rear, root);
    while(q.length > 0){
        let temp = q.shift();
         
        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);
        }
    }
     
    // If we reach here, then the tree is complete Binary 
    // Tree
    return true;
}
 
// Helper function that allocates a new node with the
// given data and null left and right pointers
function newNode(data){
    let Node = new node(data);
    return Node;
}
 
// Driver code
/* Let us construct the following Binary Tree which
    is not a complete Binary Tree
         1
        / \
        2   3
       / \   \
      4   5   6
*/
let root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
root.right.right = newNode(6);
 
if(isCompleteBT(root) == true)
    console.log("Complete Binary Tree");
else
    console.log("NOT Complete Binary Tree");
 
// This code is contributed by Yash Agarwal(yashagawral2852002)

Output

Complete Binary Tree

Time Complexity: O(n) where n is the number of nodes in a given Binary Tree
Auxiliary Space: O(h) where h is the height of the given Binary Tree

GeeksforGeeks

Improve

Previous Article

Check if given Preorder, Inorder and Postorder traversals are of same tree

Check if a binary tree is subtree of another binary tree | Set 2

Similar Reads

Check whether a binary tree is a complete tree or not | Set 2 (Recursive Solution)

A complete binary tree is a binary tree whose all levels except the last level are completely filled and all the leaves in the last level are all to the left side. More information about complete binary trees can be found here. Example:Below tree is a Complete Binary Tree (All nodes till the second last nodes are filled and all leaves are to the le

Check whether a binary tree is a full binary tree or not | Iterative Approach

Given a binary tree containing n nodes. The problem is to check whether the given binary tree is a full binary tree or not. A full binary tree is defined as a binary tree in which all nodes have either zero or two child nodes. Conversely, there is no node in a full binary tree, which has only one child node. Examples: Input : 1 / \ 2 3 / \ 4 5 Outp

Check whether a given binary tree is skewed binary tree or not?

Given a Binary Tree check whether it is skewed binary tree or not. A skewed tree is a tree where each node has only one child node or none. Examples: Input : 5 / 4 \ 3 / 2 Output : Yes Input : 5 / 4 \ 3 / \ 2 4 Output : No The idea is to check if a node has two children. If node has two children return false, else recursively compute whether subtre

Check whether a binary tree is a full binary tree or not

A full binary tree is defined as a binary tree in which all nodes have either zero or two child nodes. Conversely, there is no node in a full binary tree, which has one child node. More information about full binary trees can be found here. For Example : Recommended PracticeFull binary treeTry It! To check whether a binary tree is a full binary tre

Check if a binary tree is subtree of another binary tree using preorder traversal : Iterative

Given two binary trees S and T, the task is the check that if S is a subtree of the Tree T. For Example: Input: Tree T - 1 / \ 2 3 / \ / \ 4 5 6 7 Tree S - 2 / \ 4 5 Output: YES Explanation: The above tree is the subtree of the tree T, Hence the output is YES Approach: The idea is to traverse both the tree in Pre-order Traversal and check for each

Iterative approach to check if a Binary Tree is BST or not

Given a Binary Tree, the task is to check if the given binary tree is a Binary Search Tree or not. If found to be true, then print "YES". Otherwise, print "NO". Examples: Input: 9 / \ 6 10 / \ \ 4 7 11 / \ \ 3 5 8 Output: YES Explanation: Since the left subtree of each node of the tree consists of smaller valued nodes and the right subtree of each

Iterative Boundary Traversal of Complete Binary tree

Given a complete binary tree, traverse it such that all the boundary nodes are visited in Anti-Clockwise order starting from the root. Example: Input: 18 / \ 15 30 / \ / \ 40 50 100 20 Output: 18 15 40 50 100 20 30 Approach: Traverse left-most nodes of the tree from top to down. (Left boundary)Traverse bottom-most level of the tree from left to rig

Check whether a given binary tree is perfect or not

Given a Binary Tree, write a function to check whether the given Binary Tree is a perfect Binary Tree or not.A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at same level. Examples: The following tree is a perfect binary tree 10 / \ 20 30 / \ / \ 40 50 60 70 18 / \ 15 30 The following tree is no

Iterative Approach to check if two Binary Trees are Isomorphic or not

Given two Binary Trees we have to detect if the two trees are Isomorphic. Two trees are called isomorphic if one of them can be obtained from another by a series of flips, i.e. by swapping left and right children of a number of nodes. Any number of nodes at any level can have their children swapped. Note: Two empty trees are isomorphic. For example

Iterative Deepening Search(IDS) or Iterative Deepening Depth First Search(IDDFS)

There are two common ways to traverse a graph, BFS and DFS. Considering a Tree (or Graph) of huge height and width, both BFS and DFS are not very efficient due to following reasons. DFS first traverses nodes going through one adjacent of root, then next adjacent. The problem with this approach is, if there is a node close to root, but not in first

Article Tags :

Practice Tags :