Detect if a tree is complete binary tree

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

To understand the approach, let us first define a term ‘Full Node’. A node is ‘Full Node’ if both left and right children are not empty (or not NULL).

The approach is to do a level order traversal starting from root. In the traversal, once a node is found which is NOT a Full Node, all the following nodes must be leaf nodes.

Also, one more thing needs to be checked to handle the below case: If a node has empty left child, then the right child must be empty.

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public boolean isComplete(TreeNode root) {
    if (root == null) {
        throw new NoSuchElementException();
    }
    final Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);

    boolean incompleteDetected = false;

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

        if (node.left != null) {
            if (incompleteDetected) return false;
            queue.add(node.left);
        } else {
            incompleteDetected = true;

        // If a node has empty left child, then the right child must be empty.
          if(node.right!=null)
             return false;
        }

        if (node.right != null) {
            if (incompleteDetected) return false;
            queue.add(node.right);
        } else {
            incompleteDetected = true;
        }
    }
    return true;
}