Problem Link

https://leetcode.com/problems/check-completeness-of-a-binary-tree/

Problem Description

The root of a tree is given as input. We have to check if the given tree is a complete binary tree or not.

What is a complete binary tree?

We will understand which tree is complete or not looking at some examples of trees here.

• This is a complete binary tree. As all the nodes have both left and right children

• 

  Another three complete binary trees where the first tree's leaf nodes : [ 4,5, null, null ] and the second tree's leaf nodes : [ 4,5,6, null ]. These two are complete binary because, at the last level, all the nodes are as far left as possible. So, if the last level nodes are filled from left to right without any gap, it is considered a complete binary tree. The third tree has the same condition as the first tree, so it's also complete.

  

  

  

Let's take a look at some incomplete binary trees before we jump into the solution

• This is an incomplete binary tree because node 3 has no left child but a right child: 7.

• 

  Here node 3 has no child. So nodes 4 and 5 are supposed to have no child so this tree can be a complete binary tree. But they have children and it is an incomplete binary tree.

• 

• This is could be a complete binary tree if 3 has the right child.

So now we understand complete and incomplete binary trees, let's try to solve the problem now.

Solution

This is a binary tree and if we want to check level by level, we have to use BFS(Breadth First Search) traversal algorithm.

We have to take a queue to keep the nodes. Then pop one by one and put the node's child in the queue. If you look at the example trees, you've surely noticed that, whenever a node has a null node as a child, other nodes on that level are supposed to be null to say the tree is a complete binary tree.

So let's put this logic in codes.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        q = [root]
        while q:
            node = q.pop(0)
            # if the node is not null, append the children
            if node:
                q.append(node.left)
                q.append(node.right)
            # the node is null. TO be a complete binary tree, rest of the nodes of the queue is supposed to be null
            else:
                while q:
                    # if q.pop(0) is not null, means there are missing left child though they have right child
                    if q.pop(0):
                        return False
        return True

Complexity

We are traversing each node only once. And in the worst case, we may have to keep all the n nodes in the queue. So,

Time complexity : O(n)

Space complexity : O(n)