LeetCode Solutions Blog

Check Completeness of a Binary Tree

Number: 998

Difficulty: Medium

Paid? No

Problem Description

Determine if a binary tree is complete. 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.

Key Insights

A complete binary tree requires every level (except the last) to be fully occupied.
In the last level, nodes must fill from the left.
A level order traversal (BFS) effectively checks these conditions.
Once a missing child is encountered during BFS, all subsequent nodes must be leaves.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes, since each node is visited once. Space Complexity: O(n) in the worst-case scenario due to the queue used for BFS traversal.

Solution

We solve this problem using a breadth-first search (BFS) traversal. Traverse the tree level by level using a queue. When a node is encountered that does not have a left or right child, set a flag indicating that all following nodes must have no children. If any subsequent node has a child, the tree is not complete. This approach efficiently ensures the tree maintains the complete tree properties.

Code Solutions

# 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

# Function to check completeness of binary tree
def isCompleteTree(root: TreeNode) -> bool:
    if not root:
        return True
    
    # Initialize queue for BFS traversal
    queue = [root]
    # Flag to mark when a missing child is seen
    end = False
    
    while queue:
        node = queue.pop(0)
        
        # Check left child
        if node.left:
            if end:
                return False  # Node with left child found after a missing child has been encountered
            queue.append(node.left)
        else:
            end = True  # Future nodes must be leaves
        
        # Check right child
        if node.right:
            if end:
                return False  # Node with right child found after a missing child has been encountered
            queue.append(node.right)
        else:
            end = True  # Future nodes must be leaves
    
    return True