Check Completeness Of A Binary Tree - Leetcode Solution

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.

1