Naive Solution: Level Order Traversal with Counting

A brute-force approach involves performing a level-order traversal of the binary tree and keeping track of the number of nodes at each level. While traversing, we check if each level is full (i.e., has the maximum possible number of nodes for that level) until we encounter a level that is not full. We will know the tree is not complete binary tree if we find a node after the first gap.

Algorithm:

1. Perform a level-order traversal of the tree.
2. For each level, count the number of nodes.
3. If a level is not full, check if all subsequent levels are also not full.
4. If a level is not full and a subsequent level is full, the tree is not a complete binary tree.

Big O Analysis:

• Time Complexity: O(N), where N is the number of nodes in the tree (since we visit each node once).
• Space Complexity: O(W), where W is the maximum width of the tree (due to the queue used in level-order traversal). In the worst case (a complete binary tree), W can be N/2, so the space complexity can be considered O(N).

Optimal Solution: Using Level Order Traversal with Null Node Detection

A more efficient approach is to use a level-order traversal and look for the first null node. If we encounter a null node, then all subsequent nodes in the level order traversal must be null. If we find a non-null node after encountering the first null node, it's not a complete binary tree.

Algorithm:

1. Perform a level-order traversal of the tree.
2. Maintain a flag to indicate whether we have seen a null node.
3. If we encounter a null node, set the flag to true.
4. If we encounter a non-null node after the flag is true, return false.
5. If the entire traversal completes without finding a non-null node after a null node, return true.

Big O Analysis:

• Time Complexity: O(N), where N is the number of nodes in the tree.
• Space Complexity: O(W), where W is the maximum width of the tree.

Code Implementation (Python):

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])
    seen_null = False

    while queue:
        node = queue.popleft()

        if node is None:
            seen_null = True
        else:
            if seen_null:
                return False
            queue.append(node.left)
            queue.append(node.right)

    return True

Edge Cases:

• Empty Tree: An empty tree is considered a complete binary tree.
• Single Node Tree: A tree with only one node is a complete binary tree.
• Skewed Tree: A skewed tree (where all nodes are on one side) is generally not a complete binary tree unless it perfectly fills each level from left to right.

Example:

Consider the tree: [1,2,3,4,5,null,7]

The level-order traversal is [1, 2, 3, 4, 5, null, 7]

1. 1 is added to the queue.
2. 1 is popped. 2 and 3 are added.
3. 2 is popped. 4 and 5 are added.
4. 3 is popped. null and 7 are added.
5. 4 is popped. null and null are added.
6. 5 is popped. null and null are added.
7. null is popped. seen_null is set to True.
8. 7 is popped. Since seen_null is True, we return False.