We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Check Completeness of a Binary Tree

Difficulty: Medium

Problem Description

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 1 and 2^h nodes inclusive at the last level h.

Key Insights

  • A complete binary tree has all levels fully filled except possibly the last level.
  • In the last level, nodes must be filled from left to right without any gaps.
  • A level-order traversal (BFS) can help verify the completeness of the tree by checking the order of node insertion and ensuring no gaps appear before the last level.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree, as we visit each node once. Space Complexity: O(n), in the worst case, for the queue used in the breadth-first search (BFS).

Solution

To determine if a binary tree is complete, we can use a breadth-first search (BFS) approach. We will utilize a queue to perform the level-order traversal of the tree. As we traverse the tree, we check for any null nodes. If we encounter a null node, all subsequent nodes must also be null to satisfy the completeness condition. If we find any non-null nodes after a null node, the tree is not complete.

Code Solutions

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isCompleteTree(root: TreeNode) -> bool:
    if not root:
        return True
    
    queue = deque([root])
    end = False  # Flag to indicate if we have seen a null node
    
    while queue:
        node = queue.popleft()
        
        # If we have seen a null node, no non-null node should appear afterwards
        if node is None:
            end = True
        else:
            if end:  # If we see a non-null node after a null, return False
                return False
            queue.append(node.left)
            queue.append(node.right)
    
    return True
← Back to All Questions