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
        Queue queue = new LinkedList<>();
        queue.add(root);
        
        // 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) {
                    queue.add(curr.left);
                    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 {
                    queue.add(curr.left);
                    queue.add(curr.right);
                }
            }
        }
        
        // 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; 
    }
}