Code Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from collections import deque

class Solution:
    def isCompleteTree(self, root: TreeNode) -> bool:
        queue = deque([root])
        end = False
        while queue:
            node = queue.popleft()
            if not node:
                end = True
            else:
                if end:
                    return False
                queue.append(node.left)
                queue.append(node.right)
        return True
      

// Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// };

#include <queue>

class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        std::queue<TreeNode*> q;
        q.push(root);
        bool end = false;
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            if (!node) {
                end = true;
            } else {
                if (end)
                    return false;
                q.push(node->left);
                q.push(node->right);
            }
        }
        return true;
    }
};
      

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;

class Solution {
    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean end = false;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                end = true;
            } else {
                if (end)
                    return false;
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }
        return true;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isCompleteTree = function(root) {
    let queue = [root];
    let end = false;
    while (queue.length) {
        let node = queue.shift();
        if (!node) {
            end = true;
        } else {
            if (end) return false;
            queue.push(node.left);
            queue.push(node.right);
        }
    }
    return true;
};
      

Problem Description

Given the root of a binary tree, determine if it 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.

• You are given the root node root of the binary tree.
• Return true if the tree is complete, otherwise return false.
• Each node contains an integer value and pointers to its left and right children.
• There is only one valid answer for each test case.

Thought Process

To solve this problem, we need to understand what it means for a binary tree to be "complete". At each depth except the last, all nodes must have two children. On the last level, nodes should be filled from left to right without any gaps.

A brute-force approach might try to traverse the tree and manually check for every node's position and completeness, but this can get complicated and error-prone. Instead, we can use a level-order traversal (also known as Breadth-First Search, or BFS), which naturally visits nodes level by level from left to right.

The key insight is: if we ever find a null (missing) child during BFS, all subsequent nodes in the traversal must also be null. If we find a non-null node after a null, the tree is not complete.

Solution Approach

• Use a queue for level-order traversal: Start by enqueuing the root node.
• Track the end: Maintain a flag (let's call it end) that becomes true once we encounter the first null child.
• Traverse the tree: For each node dequeued:
  • If the node is null, set end to true.
  • If the node is not null:
    • If end is already true, return false (because a non-null node after a null means the tree is not complete).
    • Otherwise, enqueue its left and right children (even if they are null).
• If the traversal finishes without issues, return true.

This approach ensures we check the completeness property efficiently and intuitively, by leveraging the natural order of BFS.

Example Walkthrough

Let's consider the following binary tree:

        1
       / \
      2   3
     / \  /
    4  5 6
  

• We start with a queue containing [1].
• Dequeue 1: enqueue 2 and 3 ([2, 3]).
• Dequeue 2: enqueue 4 and 5 ([3, 4, 5]).
• Dequeue 3: enqueue 6 and null ([4, 5, 6, null]).
• Dequeue 4: enqueue null and null ([5, 6, null, null, null]).
• Dequeue 5: enqueue null and null ([6, null, null, null, null]).
• Dequeue 6: enqueue null and null ([null, null, null, null, null, null]).
• Now, we keep dequeuing null until the queue is empty.

At no point did we find a non-null node after a null, so the tree is complete and the function returns true.

If, for example, node 3 had a right child (say 7), the queue would eventually contain a non-null node after a null, and the function would return false.

Time and Space Complexity

• Brute-force approach:
  • Manually checking positions or using array representations can be O(N) time and space, but is less clean and more error-prone.
• Optimized (BFS) approach:
  • Time Complexity: O(N), since we visit each node exactly once.
  • Space Complexity: O(N) in the worst case, due to the queue potentially holding all nodes at the last level.

Why? Each node is enqueued and dequeued once. The queue's maximum size is proportional to the width of the tree's last level, which is O(N) in the worst case.

Summary

We solved the "Check Completeness of a Binary Tree" problem using a level-order traversal (BFS) and a simple flag to detect when a null child is encountered. This approach is efficient, easy to implement, and leverages the properties of a complete binary tree in a natural way. The solution is both elegant and practical, making it a great example of how to apply BFS to tree structure problems.