Check if a binary tree is complete
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given the root of a binary tree. Determine whether the tree is a **complete binary tree**.
A binary tree is complete if:
- Every level, except possibly the last, is completely filled.
- All nodes in the last level are as far left as possible.
### Input
- `root`: root node of a binary tree (or `null`).
### Output
- Return `true` if the tree is complete; otherwise return `false`.
### Constraints
- Number of nodes: `0..10^5`
- Node values are irrelevant to completeness.
### Notes
- Aim for an algorithm that is correct for large trees; discuss time complexity and space usage (e.g., typical BFS approach vs. any space optimizations).
Quick Answer: This question evaluates understanding of binary tree properties and traversal techniques, testing competency in data structures and algorithmic reasoning related to tree completeness.
Given level-order values with None holes, return whether the tree is complete.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([1,2,3,4,5,6],)
Expected Output: True
Explanation: Complete tree.
Input: ([1,2,3,4,None,6,7],)
Expected Output: False
Explanation: Node after gap.
Input: ([],)
Expected Output: True
Explanation: Empty tree complete.
Hints
- Use deterministic tie-breaking for prompts with multiple valid outputs.
- For design-style APIs, simulate operations with explicit inputs.