570. Check Completeness of a Binary Tree
You are given the root of a binary tree. Decide whether the tree is complete, and return true or false.
A binary tree is complete when every level is completely full, except possibly the deepest one — and on that deepest level, all nodes sit as far left as possible, with no holes before them. Equivalently: if you read the tree level by level, left to right, every real node appears before every empty slot.
This is the shape a binary heap is stored in, which is why an array can represent a heap with no gaps.
Example 1:
Input: root = [1, 2, 3, 4, 5, 6]
Output: true
Explanation: Levels 0 and 1 are full, and the last level holds 4, 5, 6 packed against the left edge — the only empty slot (3's right child) comes after every node.
Example 2:
Input: root = [1, 2, 3, 4, 5, null, 7]
Output: false
Explanation: Node 3 has no left child but does have a right child 7, so reading the last level left to right there is a hole before 7 — the tree is not complete.
Constraints:
- 1 ≤ number of nodes ≤ 100
- 1 ≤ Node.val ≤ 1000
Hints:
"Complete" is a statement about level order: scanning top to bottom, left to right, no real node may appear after an empty slot.
Do a BFS but enqueue children unconditionally — including the missing ones as null markers. The first null you pop starts the "gap"; if any real node is popped after it, the tree is not complete.
Alternative: label the root 1 and children of node i as 2i and 2i+1 (heap indexing). The tree is complete exactly when the largest label equals the number of nodes.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [1, 2, 3, 4, 5, 6]
Expected output: true