Validate complete binary tree
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given the root of a binary tree.
A **complete binary tree** is defined as a binary tree in which:
1. Every level, except possibly the last, is completely filled.
2. All nodes in the last level are as far left as possible.
Write a function that determines whether the given binary tree is complete.
Return `true` if the tree is complete, and `false` otherwise.
You may assume the tree nodes are defined as:
```text
class TreeNode {
int val;
TreeNode left;
TreeNode right;
}
```
**Examples:**
1. Input tree:
```
1
/ \
2 3
/ \ /
4 5 6
```
Output: `true` (all levels are filled except the last, and the last level is left-aligned).
2. Input tree:
```
1
/ \
2 3
/ \ \
4 5 7
```
Output: `false` (node 3 is missing a left child but has a right child, so nodes in the last level are not as far left as possible).
**Constraints:**
- The number of nodes in the tree is in the range `[1, 10^4]`.
- Node values are arbitrary integers and are not necessarily unique.
Quick Answer: This question evaluates understanding of binary tree structure and the ability to validate completeness, testing competency in tree data structures and algorithmic reasoning.
Trees are [value,left,right]. Return whether the tree is complete using level-order gap detection.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([1,[2,[4,None,None],[5,None,None]],[3,[6,None,None],None]],)
Expected Output: True
Explanation: Complete tree example.
Input: ([1,[2,[4,None,None],[5,None,None]],[3,None,[7,None,None]]],)
Expected Output: False
Explanation: Right child after missing left gap is not complete.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.