# Check Completeness of a Binary Tree LeetCode Solution

Difficulty Level Medium

## Problem Statement

Check Completeness of a Binary Tree LeetCode Solution – 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. ## Example

### Input:

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

### Output:

true ### Input:

root = [1, 2, 3, 4, 5, null, 7]

### Output:

false ## Explanation

i) Every level before the last is full (i.e levels with node values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

ii) The node with the value 7 is not as far left as possible.

## Approach

Note: A complete binary tree is a binary tree in which all the levels are completely filled except possibly the lowest one, which is filled from the left. A complete binary tree is just like a full binary tree, but with two major differences. All the leaf elements must lean towards the left.

For a complete binary tree, only the last level can have an empty node. If an empty node is seen, no valid node should be seen later. Therefore, we can put the null value in the queue and whenever we see a null value, we set a flag seenEmptyNode to be true. If later we see a valid node, then the binary tree is not a complete tree.

## Code

### Java Program for Check the Completeness of a Binary Tree

/**
* 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) {
queue.offer(root);
boolean seenNull = false;

while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0;i<size; i ++){// Traverse all nodes on this level
TreeNode curr = queue.poll();
if(curr == null) {
seenNull = true;// When found null, set the flag
}
else {
if(seenNull) return false;// If found non null node, but flag is set. Return false
queue.offer(curr.left);
queue.offer(curr.right);
}
}
}
return true;
}
}

### C++ Program for Check the Completeness of a Binary Tree

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isCompleteTree(TreeNode* root) {
if(!root) return true;
queue<TreeNode*> q;
q.push(root);
bool foundNull = false;
while(!q.empty())
{
TreeNode *curr = q.front();
q.pop();
if(curr->left)
{
if(foundNull)
return false;
q.push(curr->left);
}
else
foundNull = true;
if(curr->right)
{
if(foundNull)
return false;
q.push(curr->right);
}
else
foundNull = true;
}
return true;
}
};

## Complexity Analysis for Check Completeness of a Binary Tree LeetCode Solution

Time Complexity will be

Space Complexity will be

Translate »