958. Check Completeness of a Binary Tree - Detailed Explanation

Problem Statement

Given the root of a binary tree, determine if the tree is a complete binary tree. A complete binary tree is defined as a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

Example 1

Input:

Output: true
Explanation: All levels except the last are fully filled, and the nodes in the last level (4, 5, 6) are as far left as possible.

Example 2

Input:

Output: false
Explanation: Although the first two levels are complete, the last level is missing node 6 on the left side (node 7 appears on the right), so the tree is not complete.

Constraints

The number of nodes in the tree is in the range [1, 100].
The tree nodes contain integer values.

Hints

Level Order Traversal:
Use a breadth-first search (BFS) to traverse the tree level by level. As you traverse, keep track of whether you have encountered a null pointer (i.e., a missing child).
Null Check Principle:
Once a null is encountered in a BFS traversal, any node encountered later must also be null. If you find a non-null node after a null, the tree is not complete.

Approaches Overview

Approach 1: Breadth-First Search (BFS)

Idea:
Use a queue to perform a level order traversal.
Procedure:
1. Enqueue the root node.
2. Process nodes level by level.
3. When a null is encountered, mark that the end of the non-null nodes has been reached.
4. If a non-null node is encountered after a null, the tree is not complete.
Complexity:
- Time Complexity: O(n) since each node is visited once.
- Space Complexity: O(n) in the worst case for the queue.

Approach 2: Indexing Nodes

Idea:
Label each node with an index as if the tree were a complete binary tree. The root is index 1, its left child is 2, right child is 3, and so on.
Procedure:
1. Traverse the tree and assign an index to each node.
2. Check if the maximum index equals the number of nodes.
Complexity:
- Time Complexity: O(n) to traverse the tree.
- Space Complexity: O(n) to store the nodes in a structure (e.g., an array or queue).

The BFS approach is more intuitive for many and directly reflects the definition of a complete binary tree.

Detailed Step-by-Step Explanation (BFS Approach)

Initialization:
Create a queue and enqueue the root node.
Traverse the Tree Level by Level:
Process nodes in the queue. For each node:
- If the node is non-null, enqueue its left and right children (even if they are null).
- If a null is encountered, mark that a null has been seen.
Validation After Null:
After encountering a null, any subsequent non-null node in the BFS order indicates that the tree is not complete. This is because in a complete binary tree, once a null appears at a level, there should be no non-null nodes after that point.
Result:
If the BFS completes without encountering a non-null node after a null, the tree is complete.

Python Implementation

Python3

. . . .

Java Implementation

Java

. . . .

Complexity Analysis

Time Complexity: O(n)
Every node in the tree is visited exactly once during the BFS traversal.
Space Complexity: O(n)
In the worst case, the queue will hold all nodes at the deepest level (roughly half of the nodes).

Step-by-Step Walkthrough and Visual Example

Starting at the Root:
Enqueue the root node. Initially, the queue contains the root.
Processing Level by Level:
- Dequeue the root and enqueue its children.
- Continue processing nodes in order.
- Once a null is encountered, set the end flag.
Validation:
- If any non-null node appears after the end flag is set, immediately return false.
- If the entire tree is processed without a violation, return true.

Common Mistakes

Not Enqueueing Nulls:
It is important to enqueue nulls as placeholders to properly track the structure of the tree.
Incorrect Flag Handling:
Failing to properly set or check the end flag can result in incorrect results.
Assuming a Perfect Tree:
Remember that a complete binary tree can have the last level not completely filled, as long as the nodes are as far left as possible.

Alternative Variations

Using Node Indexing:
Instead of BFS, assign indices to nodes as if the tree were a complete binary tree. Then, check if the maximum index equals the total number of nodes.
Recursive Solutions:
Although less common for this problem, recursive approaches can be used to determine tree completeness by tracking the expected node indices.