Check Completeness of a Binary Tree

leetcode-medium

#1

Given a binary tree, return true or false based on whether the tree is a complete binary tree.

A complete binary tree is a binary tree where every level has no null nodes except the last level.


#2

The below solution uses a level order traversal.

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