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

[pastacode lang=”python” manual=”%23%20Check%20whether%20binary%20tree%20is%20complete%20or%20not%0A%20%0A%23%20A%20binary%20tree%20node%0Aclass%20Node%3A%0A%20%0A%20%20%20%20%23%20Constructor%20to%20create%20a%20new%20node%0A%20%20%20%20def%20__init__(self%2C%20data)%3A%0A%20%20%20%20%20%20%20%20self.data%20%3D%20data%20%0A%20%20%20%20%20%20%20%20self.left%20%3D%20None%0A%20%20%20%20%20%20%20%20self.right%20%3D%20None%0A%20%0A%23%20Given%20a%20binary%20tree%2C%20return%20true%20if%20the%20tree%20is%20complete%0A%23%20else%20return%20false%0Adef%20isCompleteBT(root)%3A%0A%20%20%20%20%20%0A%20%20%20%20%23%20Base%20Case%3A%20An%20empty%20tree%20is%20complete%20Binary%20tree%0A%20%20%20%20if%20root%20is%20None%3A%0A%20%20%20%20%20%20%20%20return%20True%0A%20%0A%20%20%20%20%23%20Create%20an%20empty%20queue%0A%20%20%20%20queue%20%3D%20%5B%5D%0A%20%0A%20%20%20%20%23%20Create%20a%20flag%20variable%20which%20will%20be%20set%20Trye%20%0A%20%20%20%20%23%20when%20a%20non%20ful%20node%20is%20seen%0A%20%20%20%20flag%20%3D%20False%0A%20%0A%20%20%20%20%23%20Do%20level%20order%20traversal%20using%20queue%0A%20%20%20%20queue.append(root)%0A%20%20%20%20while(len(queue)%20%3E%200)%3A%0A%20%20%20%20%20%20%20%20tempNode%20%3D%20queue.pop(0)%20%23%20Dequeue%20%0A%20%0A%20%20%20%20%20%20%20%20%23%20Check%20if%20left%20child%20is%20present%0A%20%20%20%20%20%20%20%20if%20(tempNode.left)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20If%20we%20have%20seen%20a%20non%20full%20node%2C%20and%20we%20see%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20a%20node%20with%20non-empty%20left%20child%2C%20then%20the%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20given%20tree%20is%20not%20a%20complete%20binary%20tree%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20flag%20%3D%3D%20True%20%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20False%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Enqueue%20left%20child%0A%20%20%20%20%20%20%20%20%20%20%20%20queue.append(tempNode.left)%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20If%20this%20a%20non-full%20node%2C%20set%20the%20flag%20as%20true%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20flag%20%3D%20True%0A%20%0A%20%20%20%20%20%20%20%20%23%20Check%20if%20right%20cild%20is%20present%0A%20%20%20%20%20%20%20%20if(tempNode.right)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20If%20we%20have%20seen%20a%20non%20full%20node%2C%20and%20we%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20see%20a%20node%20with%20non-empty%20right%20child%2C%20then%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20the%20given%20tree%20is%20not%20a%20compelete%20BT%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20flag%20%3D%3D%20True%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20False%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Enqueue%20right%20child%0A%20%20%20%20%20%20%20%20%20%20%20%20queue.append(tempNode.right)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20If%20this%20is%20non-full%20node%2C%20set%20the%20flag%20as%20True%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20flag%20%3D%20True%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%23%20If%20we%20reach%20here%2C%20then%20the%20tree%20is%20compelete%20BT%0A%20%20%20%20return%20True%0A%20%0A%20%0A%23%20Driver%20program%20to%20test%20above%20function%0A%20%0A%22%22%22%20Let%20us%20construct%20the%20following%20Binary%20Tree%20which%0A%20%20%20%20%20%20is%20not%20a%20complete%20Binary%20Tree%0A%20%20%20%20%20%20%20%20%20%20%20%201%0A%20%20%20%20%20%20%20%20%20%20%2F%20%20%20%5C%0A%20%20%20%20%20%20%20%20%202%20%20%20%20%203%0A%20%20%20%20%20%20%20%20%2F%20%5C%20%20%20%20%20%5C%0A%20%20%20%20%20%20%204%20%20%205%20%20%20%20%206%0A%20%20%20%20%22%22%22%0Aroot%20%3D%20Node(1)%0Aroot.left%20%3D%20Node(2)%0Aroot.right%20%3D%20Node(3)%0Aroot.left.left%20%3D%20Node(4)%0Aroot.left.right%20%3D%20Node(5)%0Aroot.right.right%20%3D%20Node(6)%0A%20%0Aif%20(isCompleteBT(root))%3A%0A%20%20%20%20print%20%22Complete%20Binary%20Tree%22%0Aelse%3A%0A%20%20%20%20print%20%22NOT%20Complete%20Binary%20Tree%22%0A%20%0A%23%20This%20code%20is%20contributed%20by%20Nikhil%20Kumar%20Singh(nickzuck_007)” message=”” highlight=”” provider=”manual”/]

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:

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