958.Check_Completeness_of_a_Binary_Tree(Medium).md

958. Check Completeness of a Binary Tree (Medium)

Date and Time: Dec 15, 2024, 22:55 (EST)

Link: https://leetcode.com/problems/check-completeness-of-a-binary-tree

Question:

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.

Example 1:

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.

Example 2:

Input: root = [1,2,3,4,5,null,7]

Output: false

Explanation: The node with value 7 isn't as far left as possible.

Constraints:

• The number of nodes in the tree is in the range [1, 100].

• 1 <= Node.val <= 1000

Walk-through:

Complete Binary Tree means there is no null node between any 2 nodes.

So we can run BFS to check each level's nodes, if there is a null node, we mark seenNull = True. Then, if we have other nodes and seenNull = True, we return False.

Python Solution:

# 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:
        # Run BFS to check if a null node is between two nodes
        # Set seenNull = True when a node is null, if seenNull is True and we have other nodes, return False

        # TC: O(n), n is total nodes, SC: O(n)
        seenNull = False
        deque = collections.deque([root])
        while deque:
            node = deque.popleft()
            # Check if current node is null
            if not node:
                seenNull = True
            else:
                # Check if we encounter null node before
                if seenNull:
                    return False
                deque.append(node.left)
                deque.append(node.right)
        return True

Time Complexity: $O(n)$
Space Complexity: $O(n)$