# Python Programming-Check whether a given Binary Tree is Complete or not

Check whether given binary tree complete not Given a Binary Tree, write a function to check whether the given Binary Tree is Complete Binary Tree or not.

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

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

READ  Java Programming - Longest Bitonic Subsequence

Auxiliary Space: O(n) for queue.

#### Venkatesan Prabu

Wikitechy Founder, Author, International Speaker, and Job Consultant. My role as the CEO of Wikitechy, I help businesses build their next generation digital platforms and help with their product innovation and growth strategy. I'm a frequent speaker at tech conferences and events.