Leetcode 958. Check Completeness of a Binary Tree

Problem Explanation

A binary tree is a tree-like data structure where each node has at most two children - a left child and a right child. A complete binary tree is a binary tree where all the levels, except possibly the last, are completely filled, and all the nodes in the last level are as far left as possible.

Given a binary tree, the problem is to decide if it is a complete binary tree or not.

Consider the following tree:

1
2
3   1
4  / \
5 2   3

This binary tree is a complete binary tree. However, if we have a tree like the following:

1
2
3   1
4  / \
5 2   3
6/ \
74   5

This tree is also a complete binary tree.

Solution Explanation

This problem can be solved using a breadth-first search (BFS) strategy. In BFS, we visit all the nodes level by level from left to right. We can use a queue, a FIFO (First-In-First-Out) data structure, to hold the nodes as we traverse the tree.

Starting with the root node, we inspect the children and enqueue them. If any NULL value is encountered before we have finished inspecting all the nodes, it means that not all the nodes on the last level are as far left as possible, so the tree is not complete. If we encounter NULL values only after inspecting all the nodes, meaning that the NULL values come only after there are no more nodes to inspect, the tree will be complete.

Solution in C++

1
2cpp
3class Solution {
4 public:
5  bool isCompleteTree(TreeNode* root) {
6    if (root == nullptr)
7      return true;
8
9    queue<TreeNode*> q{{root}};
10
11    while (q.front() != nullptr) {
12      TreeNode* node = q.front();
13      q.pop();
14      q.push(node->left);
15      q.push(node->right);
16    }
17
18    while (!q.empty() && q.front() == nullptr)
19      q.pop();
20
21    return q.empty();
22  }
23};

Solution in Java

1
2java
3public class Solution {
4    public boolean isCompleteTree(TreeNode root) {
5        Queue<TreeNode> q = new LinkedList<>();
6        q.add(root);
7        
8        while (q.peek() != null) {
9            TreeNode node = q.poll();
10            q.add(node.left);
11            q.add(node.right);
12        }
13        
14        while (!q.isEmpty() && q.peek() == null) { 
15            q.poll();
16        }
17        
18        return q.isEmpty();
19    }
20}

Solution in Python

1
2python
3class Solution:
4    def isCompleteTree(self, root):
5        if root is None:
6            return True
7        
8        q = [root]
9        while q[0] is not None:
10            node = q.pop(0)
11            q.append(node.left)
12            q.append(node.right)
13        
14        while len(q) > 0 and q[0] is None:
15            q.pop(0)
16        
17        return len(q) == 0

Solution in JavaScript

1
2javascript
3var isCompleteTree = function(root) {
4    if (root === null) {
5        return true;
6    }
7    
8    let queue = [root];    
9    while (queue[0] !== null) {
10        let node = queue.shift();
11        queue.push(node.left);
12        queue.push(node.right);
13    }
14    
15    while (queue.length > 0 && queue[0] === null) {
16        queue.shift();
17    }
18    
19    return queue.length === 0;
20};

Solution in C#

1
2csharp
3public class Solution {
4    public bool IsCompleteTree(TreeNode root) {
5        if (root == null) {
6            return true;
7        }
8
9        Queue<TreeNode> q = new Queue<TreeNode>();
10        q.Enqueue(root);
11        while (q.Peek() != null) {
12            TreeNode node = q.Dequeue();
13            q.Enqueue(node.left);
14            q.Enqueue(node.right);
15        }
16
17        while (q.Count > 0 && q.Peek() == null) {
18            q.Dequeue();
19        }
20        
21        return q.Count == 0;
22    }
23}

In each of these solutions, we start by checking if the root node is null. If it is, the tree is trivially complete. If not, we add it to the queue. We proceed to dequeue the elements from the front of the queue and enqueue their left and right children. If we encounter a null child, we continue removing elements from the queue until we find a non-null child or exhaust the queue. If we find a non-null child, the tree isn't complete. Otherwise, it is complete.## Time and Space Complexity Analysis

The time and space complexity of this solution is O(N), where N is the total number of nodes in the input binary tree.

The time complexity of O(N) is because each node is processed once during the breadth-first search. For each node, a constant amount of work needs to be done: removing it from the queue and then inserting zero, one, or two nodes into the queue.

The space complexity is also O(N). This is because each node can be in the queue at most once, so the number of nodes in the queue at any point in time can be at most N. Therefore, the maximum space used by the queue throughout the execution of the algorithm is proportional to N, leading to a space complexity of O(N).

Conclusion

To summarize, we can determine whether a binary tree is complete, by using a breadth-first search strategy to verify whether there's a non-null node after a null node. This solution is efficient with a time and space complexity of O(N). It's also straightforward to implement in multiple programming languages like C++, Java, Python, JavaScript and C#. This approach works well because BFS processes nodes in a top-down, left-to-right order, which ensures any violation of the complete binary tree property is detected as soon as possible. Applying BFS to this problem is also logical to validate the given definition of a complete binary tree.