Check Completeness of a Binary Tree

Problem Id: 958 Difficulty: Medium Tag: Tree


Intuition

We could use a BFS to solve this problem. First, BFS would help us to get the additional row which is not full. If there are no such row, return True. If that row has None in the middle of the values, return False.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque


class Solution:
    def isCompleteTree(self, root: TreeNode) -> bool:
        queue = deque([root])
        while queue:
            node = queue.popleft()
            if node is None:
                break
            queue.append(node.left)
            queue.append(node.right)
        for left in queue:
            if left is not None:
                return False
        return True