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 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 a term ‘Full Node’. A node is ‘Full Node’ if both left and right children are not empty (or not NULL).

[ad type=”banner”] The approach is to do a level order traversal starting from 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 empty left child, then the right child must be empty.

Python Programming

# Check whether 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 Trye 
    # when a non ful 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 cild 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 compelete 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 compelete 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)

Output:

NOT Complete Binary Tree

Time Complexity: O(n) where n is the number of nodes in given Binary Tree

Auxiliary Space: O(n) for queue.

[ad type=”banner”]

Categorized in:

CodingData StructuresPYTHONQueue

Tagged in:

, , , , , , , , , , , , , ,