Check completeness of Binary tree

958.Check Completeness of a Binary Tree

Tree

Binary Tree

BFS

Problem Statement:

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.

Example:

Input:

[1,2,3,4,5,6]

→

Output:

true

Java Solution:

// Essentially can't have null node then a non null node after
// Since nodes in last row must be as far left as possible
public boolean isCompleteTree(TreeNode root) {
    if (root == null) {
        return true;
    }

    boolean nullNodeFound = false;
    Queue q = new LinkedList<>();
    q.offer(root);

    while (!q.isEmpty()) {
        TreeNode node = q.poll();

        if (node == null) {
            nullNodeFound = true;  // Mark that we've found a null node
        } else {
            if (nullNodeFound)  // If we find a non-null after null, tree is not complete
                return false;
            q.offer(node.left);
            q.offer(node.right);
        }
    }
    return true;
}

Python Solution:

def isCompleteTree(self, root: TreeNode) -> bool:
    if not root:
        return True
        
    queue = deque([root])
    null_found = False
    
    while queue:
        node = queue.popleft()
        
        if node is None:
            null_found = True
        else:
            if null_found:  # Found node after null
                return False
            queue.append(node.left)
            queue.append(node.right)
            
    return True

C++ Solution:

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

Complexity:

Time: O(n) where n is number of nodes
Space: O(w) where w is maximum width of tree