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.