# Solution For Check Completeness Of A Binary Tree

Problem Statement:

Given the root of a binary tree, determine if it is a complete binary tree.

A binary tree is complete if 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: [1,2,3,4,5,6]

Output: true

Explanation: Every level except the last is full, and the last level has all nodes as far left as possible.

Solution:

To determine if a binary tree is complete, we need to check if the nodes are following the rule of having nodes in last level added from left to right without leaving any gaps. Let’s define few terms for better understanding-

height = ht

Nodes in a complete tree = 2^ht – 1

Nodes in the last level = k (in a non-empty tree)

In a complete tree, the minimum number of nodes in the last level is “1” and the maximum is 2^k-1.

The easiest way to check this is to sweep across the tree from left to right and check if any gap exists in between. Once we find a gap, it should be the last level, and all the nodes that come next should be null pointers. If we find any node after the null pointers, we can declare that the tree is not complete. Otherwise, the tree will be complete.

Algorithm:

1. Calculating the height or maximum levels of the tree.
2. Perform a level order traversal, and for each node after the first null child:
a. If flag is true, return False, as we’ve already skipped blank spots
b. Set flag to true if one null child is found
3. If we’ve never returned False on a node w/ 1 non-null child, return True.

Code implementation:

In order to implement the above algorithm, we will write a recursive function in Python:

def isCompleteTree(root: TreeNode) -> bool:

``````def check(root, i, n):
if not root:
return True
if i >= n:
return False
return (check(root.left,2*i+1,n) and check(root.right,2*i+2,n))

# Calculating the number of nodes and height in the tree
count = 0
height = 0
nodeCount = [0]
q = [root]
while q:
temp = q.pop(0)
count += 1
if temp.left:
q.append(temp.left)
if temp.right:
q.append(temp.right)
if not q:
nodeCount.append(count)
if count == 2**height:
height += 1
count = 0
n = nodeCount[-1]

# Perform a level order traversal and check for gaps
return check(root,0,n)
``````

Time Complexity:

In the worst case, this algorithm will traverse the complete binary tree (O(n)nodes) once. Therefore, the time complexity of this algorithm is O(n).

Space Complexity:

The space required for the queue is O(n), which is the maximum size of the queue while traversing the tree.

Summary:

In this problem, we have learned how to determine whether a binary tree is a complete binary tree or not. We identified that a complete binary tree has no gaps in the last level, and we have designed an algorithm that uses a level order traversal to check for gaps and verify whether a binary tree is complete. The time and space complexity of our algorithm is O(n), where n is the number of nodes in the binary tree.

## Step by Step Implementation For Check Completeness Of A Binary Tree

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isCompleteTree(TreeNode root) {
// Base case
if (root == null) {
return true;
}

// Create a queue and add the root node

// Variable to keep track of whether we have seen a non-full node
boolean seenNonFull = false;

// Iterate over the queue until it's empty
while (!queue.isEmpty()) {
// Get the node at the front of the queue
TreeNode curr = queue.remove();

// If we have seen a non-full node, we should only see null nodes from here on out
if (seenNonFull) {
if (curr.left != null || curr.right != null) {
return false;
}
}
// Otherwise, we need to check if the current node is non-full
else {
// Case 1: Current node is a leaf node (has no children)
if (curr.left == null && curr.right == null) {
continue;
}
// Case 2: Current node has only a left child
else if (curr.left != null && curr.right == null) {
seenNonFull = true;
}
// Case 3: Current node has only a right child
else if (curr.left == null && curr.right != null) {
return false;
}
// Case 4: Current node has both left and right children
else {
}
}
}

// If we get to this point, that means we have successfully traversed the tree
// and all nodes are either full or we have only seen null nodes after encountering
// a non-full node. Therefore, the tree is complete.
return true;
}
}```
```# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def isCompleteTree(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
# if the tree is empty, return true
if not root:
return True

# create a queue and add the root node
queue = [root]

# set a flag to track if we have seen a non-full node
seen_nonfull = False

# while the queue is not empty
while queue:

# get the next node from the queue
node = queue.pop(0)

# if we have seen a non-full node, and the current node is not a leaf
# (i.e. it has at least one child), then the tree is not complete
if seen_nonfull and (node.left or node.right):
return False

# if the current node has a left child, add it to the queue
if node.left:
queue.append(node.left)

# otherwise, we have seen a non-full node
else:
seen_nonfull = True

# if the current node has a right child, add it to the queue
if node.right:
queue.append(node.right)

# otherwise, we have seen a non-full node
else:
seen_nonfull = True

# if we reach this point, the tree is complete
return True```
```// given a binary tree, check if it is a complete binary tree or not

function isCompleteBinaryTree(root) {
// if the tree is empty, it is complete
if (!root) return true;

// get the height of the tree
let height = getHeight(root);

// get the number of nodes in the tree
let nodeCount = getNodeCount(root);

// if the node count is equal to 2^height - 1, it is a complete binary tree
return nodeCount == Math.pow(2, height) - 1;
}

// get the height of the tree
function getHeight(root) {
// if the tree is empty, the height is 0
if (!root) return 0;

// recursively get the height of the left and right subtrees
let leftHeight = getHeight(root.left);
let rightHeight = getHeight(root.right);

// return the height of the tree (the larger of the two subtrees + 1)
return Math.max(leftHeight, rightHeight) + 1;
}

// get the number of nodes in the tree
function getNodeCount(root) {
// if the tree is empty, the node count is 0
if (!root) return 0;

// recursively get the node count of the left and right subtrees
let leftCount = getNodeCount(root.left);
let rightCount = getNodeCount(root.right);

// return the node count of the tree (the sum of the left and right subtrees)
return leftCount + rightCount + 1;
}```
```/**
* 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) {
// Base case
if (root == nullptr) {
return true;
}

// Create an empty queue
queue q;

// Enqueue root node
q.push(root);

// Iterate while there are nodes in the queue
while (!q.empty()) {
// Dequeue a node from the queue
TreeNode* curr = q.front();
q.pop();

// If this node is NULL, then we have encountered
// a leaf node. Since the tree is supposed to be
// complete, we should not encounter any more
// nodes after this.
if (curr == nullptr) {
break;
}

// Enqueue the left and right child nodes of
// the current node
q.push(curr->left);
q.push(curr->right);
}

// Now, we check if the queue is empty. If it is
// empty, then the tree is complete. If not, then
// the tree is not complete.
return q.empty();
}
};```
```/**
* Definition for a binary tree node.
* public class TreeNode {
*     public int val;
*     public TreeNode left;
*     public TreeNode right;
*     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
public class Solution {
public bool IsCompleteTree(TreeNode root) {
// Base case
if (root == null)
return true;

// Create an empty queue
Queue queue = new Queue();

// Enqueue Root
queue.Enqueue(root);

// While there are nodes in the queue
while (queue.Count != 0)
{
// Dequeue a node from the queue
TreeNode node = queue.Dequeue();

/* If this is the last node of the level,
enqueue a marker for level ending. */
if (node.left == null && node.right != null)
return false;

if (node.right != null)
queue.Enqueue(node.right);

if (node.left != null)
queue.Enqueue(node.left);
/* If this a non-full node, make sure no node
exists after it */
else if (node.left == null && node.right == null)
{
if (queue.Count != 0)
return false;
}
}

// The tree is complete
return true;
}
}```

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]