Check Completeness of a Binary Tree

Leetcode Daily Challenge (15th March, 2023)

15 March, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

Problem Statement:-

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.

Link: https://leetcode.com/problems/check-completeness-of-a-binary-tree/

Problem Explanation with examples:-

Example 1

Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

Example 2

Input: root = [1,2,3,4,5,null,7]
Output: false
Explanation: The node with value 7 isn't as far left as possible.

Constraints

The number of nodes in the tree is in the range [1, 100].
1 <= Node.val <= 1000

Intuition:-

Again a binary tree problem so we will use recursion.
We need to make sure that all the levels except the leaf level are not empty.
The leaf level may or may not be empty.
Also, the nodes should be as left as possible.
So, something which goes level-wise and also left to right.
What comes to your mind? ... BFS.
So, we will use BFS to solve this problem and will keep track that no null value is encountered in between the levels or in the leaf level. Null values are allowed at the leaf level but not in between existing node values.

Solution:-

Create a queue or list.
Append the root node to it.
Create a boolean variable nullEncountered and set it to False.
While the queue is not empty, pop the first element and store it in a variable node.
If the node is null, set nullEncountered to True.
Else, if nullEncountered is True, return False as the tree is not complete.
Else, append the left and right child of the node to the queue.
Return True after the queue is empty as the tree is complete

Code:-

JAVA Solution

public class Solution {
    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);

        boolean nullEncountered = false;

        while (!q.isEmpty()) {
            TreeNode node = q.remove();
            if (node == null) {
                nullEncountered = true;
            } else {
                if (nullEncountered) return false;
                q.add(node.left);
                q.add(node.right);
            }
        }
        return true;
    }
}

Python Solution

class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        q = []
        q.append(root)

        nullEncountered = False

        while q:
            node = q.pop(0)
            if not node:
                nullEncountered = True
            else:
                if nullEncountered: return False
                q.append(node.left)
                q.append(node.right)
        return True

Complexity Analysis:-

TIME:-

Time complexity is O(N) where n is the number of nodes in the binary tree. This is because the code visits each node in the tree once and performs constant time operations for each node. The while loop will run n times, as it will process all the nodes in the tree. The constant time operations include appending a node to the queue, popping the first node from the queue, and checking if a node is null or not.

SPACE:-

Space complexity of this code is also O(N), which is the maximum size of the queue. In the worst case scenario, the queue will contain all the nodes of the last level of the binary tree, which can be at most n/2 nodes. Therefore, the space complexity is proportional to the number of nodes in the tree.