Check completeness of a binary tree

We will use BFS for level order traversal. We will add children to the BFS queue, if it's a complete tree, we should not have any node once we encounter a null node.

# 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 = collections.deque([root])
        while q:
            node = q.pop()
            if not node:
                break
            q.appendleft(node.left)
            q.appendleft(node.right)
        return not any(q)

Time complexity: O(n)
Space complexity: O(n)