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:

       1
      / \
     2   3
    / \  /
   4  5 6

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:

       1
      / \
     2   3
    / \   \
   4   5   7

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

1. 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).

2. 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)

1. Initialization:
   Create a queue and enqueue the root node.

2. 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.

3. 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.

4. Result:
   If the BFS completes without encountering a non-null node after a null, the tree is complete.

Python Implementation