Check Completeness of a Binary Tree LeetCode Solution

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 2^h nodes inclusive at the last level h.

Example

Test Case 1:

Input:

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

Output:

true

Test Case 2:

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<TreeNode> queue = new LinkedList();
        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 $O(n),$$where\; n\; is\; the\; number\; of\; nodes\; in\; the\; tree.$

Space Complexity will be $O(t),$$where\; n\; is\; the\; number\; of\; nodes\; in\; the\; tree.$

Reference: https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees