Check Completeness of a Binary Tree

lcpy gen -n 958   # by problem number
lcpy gen -s check_completeness_of_a_binary_tree   # by problem name

Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

Input: root = [1,2,3,4,5,null,7]
Output: false
Explanation: The node with value 7 isn't as far left as possible.

from collections import deque

from leetcode_py import TreeNode


class Solution:
    # Time: O(n)
    # Space: O(n)
    def is_complete_tree(self, root: TreeNode[int] | None) -> bool:
        if root is None:
            return True
        queue: deque[TreeNode[int] | None] = deque([root])
        seen_hole = False
        while queue:
            node = queue.popleft()
            if node is None:
                seen_hole = True
                continue
            if seen_hole:
                # A node appeared after a gap: not complete
                return False
            queue.append(node.left)
            queue.append(node.right)
        return True