L958 Validate a complete binary tree

Problem:

Validate a complete binary tree

at most has two nodes and as far left as possible

Solution:

O(n)

• do a level order traversal starting from the root.

  • In the traversal, once a node is found which is NOT a Full Node, all the following nodes must be leaf nodes.

  • If a node has an empty left child, then the right child must be empty.

  when a non full node is seen, a flag variable which will be set true

public boolean isComplete(TreeNode root){
    if(root == null) return true;
    Queue<TreeNode> queue = new ArrayList<>();
    boolean flag = false; 
    
    queue.offer(root);
    while(!queue.isEmpty()){
        TreeNode pollNode = queue.poll();
        if(pollNode != null){
            if(flag == true) return false;
            queue.offer(pollNode.left);
            queue.offer(pollNode.right);
        }else{
            flag = true;
        }
    }
    return true;
}