Given the root of a binary tree, determine if it is a complete binary tree.

In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

Input: root = [1,2,3,4,5,null,7]
Output: false
Explanation: The node with value 7 isn't as far left as possible.

The number of nodes in the tree is in the range [1, 100].
1 <= Node.val <= 1000

• There is no node in the given tree if the root node is null. We return true.
• Create a boolean variable nullNodeFound to track whether or not a null node has been visited yet. We initialize it to false.
• Intiailize a TreeNode queue q and push root into it.
• While the queue is not empty:
• Dequeue the first element node from the queue.
• If node == null, mark nullNodeFound = true.
• Otherwise, if node is not null, we check to see if we have previously visited a null node. If nullNodeFound == true, it means we have node which is not null after visiting a null node. As a result, we return false in such a case. Otherwise, if we have not visited a null node yet, we push node.left and then node.right into the queue.
• We are able to traverse the entire tree without seeing a non-null node after a null node, we return true.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isCompleteTree(TreeNode root) {
        if(root ==null) return true;

        boolean nullFound = false;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode n = q.poll();
            if(n == null){
                nullFound = true;
            }
            else{
                //null found before the last element
                if(nullFound) return false;
                q.offer(n.left);
                q.offer(n.right);

            }
        }
        return true;
    }
}

Here n is the number of nodes.

Time complexity: O(n).

Each queue operation in the BFS algorithm takes O(1) time, and a single node can only be pushed once, leading to O(n) operations for n nodes. Since we have directed edges, each edge can only be iterated once, resulting in O(e) operations total while visiting all nodes, where e is the number of edges. Because the given graph is a tree, there are n−1 edges, so O(n+e)=O(n). Space complexity: O(n).

The last or second last level would have the most nodes (the last level can have multiple null nodes) in a complete binary tree. Because we are iterating by level, the BFS queue will be most crowded when all of the nodes from the last level (or second last level) are in the queue. Assume we have a complete binary tree with height h and a fully filled last level having 2 h nodes. All the nodes at each level add up to 1+2+4+8+...+2 h =n. This implies that 2 h+1 −1=n, and thus 2 h =(n+1)/2. Because the last level h has 2 h nodes, the BFS queue will have (n+1)/2=O(n) elements in the worst-case scenario.