Learning On the Way

958. Check Completeness of a Binary Tree

Given the root of a binary tree, determine if it is a complete binary tree.

In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1and 2hnodes inclusive at the last level h.

Short and Smart

def isCompleteTree(self, root: Optional[TreeNode]) -> bool: 
    dq = collections.deque([root]) 
     
    while True: 
        node = dq.popleft() 
        if not node: 
            return not any(dq) 
        dq.append(node.left) 
        dq.append(node.right)

Use node numbering system.

Root is 1. Left is parent * 2, right is parent * 2 + 1

def isCompleteTree(self, root: Optional[TreeNode]) -> bool: 
    filled = set() 
     
    def visit(node, val): 
        if not node: 
            return 
        filled.add(val) 
        visit(node.left, val * 2) 
        visit(node.right, val * 2 + 1) 
         
    visit(root, 1) 
     
    seenFalse = False 
    for i in range(1, max(filled) + 1): 
        if i not in filled: 
            seenFalse = True 
        elif seenFalse: 
            return False 
    return True