# LeetCode 958: Check Completeness of a Binary Tree

## Problem Restatement

We are given the root of a binary tree.

We need to determine whether the tree is a complete binary tree.

A complete binary tree has these properties:

1. Every level except possibly the last is completely filled.
2. All nodes in the last level are as far left as possible.

Return `true` if the tree is complete. Otherwise, return `false`.

The official problem states this exact definition: every level except possibly the last is completely filled, and all nodes in the last level are as far left as possible.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `root`, the root of a binary tree |
| Output | `true` if the tree is complete, otherwise `false` |
| Tree rule | No node may appear after a missing position in level-order traversal |

Example function shape:

```python
def isCompleteTree(root: Optional[TreeNode]) -> bool:
    ...
```

## Examples

Example 1:

```python
root = [1, 2, 3, 4, 5, 6]
```

Output:

```python
True
```

The tree is:

```text
        1
      /   \
     2     3
    / \   /
   4   5 6
```

The last level is filled from left to right. There is no gap before an existing node.

Example 2:

```python
root = [1, 2, 3, 4, 5, None, 7]
```

Output:

```python
False
```

The tree is:

```text
        1
      /   \
     2     3
    / \     \
   4   5     7
```

There is a missing left child under node `3`, but a right child `7` exists after that missing position.

That violates completeness.

## First Thought: Check Each Level

A complete tree is filled level by level from left to right.

So one idea is to inspect every level and check whether:

1. All levels before the last are full.
2. The last level has no gaps.

This can work, but it requires careful bookkeeping.

There is a simpler way: use level-order traversal and watch for the first missing node.

## Key Insight

In a complete binary tree, once we see a missing child position during BFS, every later position must also be missing.

This is the core rule:

```python
after seeing None, we must never see another real node
```

Why?

BFS visits nodes in level-order from left to right.

A missing position means there is a gap.

If a real node appears after that gap, then the tree has a node farther right while an earlier position is empty. That cannot happen in a complete binary tree.

## Algorithm

Use a queue for BFS.

1. Put `root` into the queue.
2. Keep a boolean flag:

```python
seen_missing = False
```

3. While the queue is not empty:
   - Pop the next item.
   - If it is `None`, set `seen_missing = True`.
   - Otherwise:
     - If `seen_missing` is already `True`, return `False`.
     - Push its left child.
     - Push its right child.
4. If BFS ends without finding a real node after a missing position, return `True`.

## Correctness

BFS visits binary tree positions in the exact order required by completeness: level by level, left to right.

In a complete binary tree, all existing nodes must appear before all missing positions in this traversal. Once a position is missing, every later position must also be missing.

The algorithm records whether it has already seen a missing position.

If it later sees a real node, then a node exists after a gap in level-order order. That means the last level is not filled from left to right, or an earlier level is incomplete. In both cases, the tree is not complete, so returning `False` is correct.

If the algorithm finishes without seeing any real node after a missing position, then all real nodes appeared before all missing positions in level-order traversal. Therefore, every level before the last is filled, and the last level is filled from left to right. So the tree is complete.

## Complexity

Let `n` be the number of nodes.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each real node is processed once |
| Space | `O(n)` | The queue may hold nodes and missing child positions |

## Implementation

```python
from collections import deque
from typing import Optional

# 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:
        queue = deque([root])
        seen_missing = False

        while queue:
            node = queue.popleft()

            if node is None:
                seen_missing = True
                continue

            if seen_missing:
                return False

            queue.append(node.left)
            queue.append(node.right)

        return True
```

## Code Explanation

We start BFS from the root:

```python
queue = deque([root])
```

The flag tracks whether a missing position has appeared:

```python
seen_missing = False
```

For each item popped from the queue:

```python
node = queue.popleft()
```

If the item is missing:

```python
if node is None:
    seen_missing = True
    continue
```

we mark that all later items must also be missing.

If the item is a real node after a missing position:

```python
if seen_missing:
    return False
```

then the tree has a gap before an existing node, so it is incomplete.

Otherwise, we add both child positions:

```python
queue.append(node.left)
queue.append(node.right)
```

We add `None` children deliberately. They represent missing positions in level-order traversal.

If traversal ends cleanly:

```python
return True
```

the tree is complete.

## Testing

```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 build_tree(values):
    if not values:
        return None

    root = TreeNode(values[0])
    queue = deque([root])
    i = 1

    while queue and i < len(values):
        node = queue.popleft()

        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1

        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1

    return root

def run_tests():
    s = Solution()

    root = build_tree([1, 2, 3, 4, 5, 6])
    assert s.isCompleteTree(root) is True

    root = build_tree([1, 2, 3, 4, 5, None, 7])
    assert s.isCompleteTree(root) is False

    root = build_tree([1])
    assert s.isCompleteTree(root) is True

    root = build_tree([1, 2, 3, 4, None, 6, 7])
    assert s.isCompleteTree(root) is False

    root = build_tree([1, 2, 3, 4, 5])
    assert s.isCompleteTree(root) is True

    root = build_tree([1, 2, 3, None, None, 6, 7])
    assert s.isCompleteTree(root) is False

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1,2,3,4,5,6]` | Complete tree with last level partially filled |
| `[1,2,3,4,5,None,7]` | Existing node after a gap |
| `[1]` | Single-node tree |
| `[1,2,3,4,None,6,7]` | Gap in the last level before later nodes |
| `[1,2,3,4,5]` | Valid left-filled last level |
| `[1,2,3,None,None,6,7]` | Earlier missing children before later nodes |