Check Completeness of a Binary Tree

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.

Approach 1:

class Solution {
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }

        boolean checkNullNode = false;
        Queue queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode currNode = queue.poll();
            if (currNode == null) {
                checkNullNode = true;
            } else {
                if (checkNullNode)
                    return false;
                queue.offer(currNode.left);
                queue.offer(currNode.right);
            }
        }
        return true;
    }
}
                

Time Complexity: O(n) and Space Complexity: O(n)

The problem Check Completeness of a Binary Tree involves verifying if a binary tree is complete. A binary tree is considered complete if all its levels, except possibly the last, are fully filled, and all nodes are as far left as possible.

Problem Statement

Given a binary tree, determine if it is a complete binary tree. A complete binary tree has two main properties:

• All levels of the tree are completely filled except possibly for the last level.
• At the last level, all nodes are as left as possible.

You need to return true if the tree is complete and false otherwise.

Approach to Solve the Problem

The solution involves performing a level-order traversal (Breadth-First Search or BFS) of the binary tree. During this traversal, we can use a queue to ensure that the nodes are visited in the correct order. If at any point we encounter a non-full node at the last level or any node that violates the completeness property, we can conclude that the tree is not complete.

Steps to Solve:

1. Perform a level-order traversal using a queue.
2. During traversal, mark nodes as visited.
3. If we encounter a node that has a child after an incomplete node (i.e., a null child), we return false immediately.
4. After traversal, if no violations were found, return true.

Implementation

Here is the Python implementation:

from collections import deque

class Solution:
    def isCompleteTree(self, root):
        if not root:
            return True
        
        queue = deque([root])
        reached_end = False
        
        while queue:
            node = queue.popleft()
            
            if node:
                if reached_end:
                    return False
                queue.append(node.left)
                queue.append(node.right)
            else:
                reached_end = True
        
        return True
        

Here is the Java implementation:

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        Queue queue = new LinkedList<>();
        queue.offer(root);
        boolean reachedEnd = false;
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            
            if (node != null) {
                if (reachedEnd) {
                    return false;
                }
                queue.offer(node.left);
                queue.offer(node.right);
            } else {
                reachedEnd = true;
            }
        }
        
        return true;
    }
}
        

Example

Consider the binary tree:

            Tree Structure:
                1
               / \
              2   3
             / \   / 
            4   5 6   
        

In this case, the tree is incomplete because node 3 has no right child, but node 5 appears after node 3, violating the completeness condition. The answer is false.

Now consider the following tree:

            Tree Structure:
                1
               / \
              2   3
             / \   / \
            4   5 6   7
        

This is a complete binary tree, so the answer is true.

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes in the tree. We perform a level-order traversal that visits each node once.

Space Complexity: O(n), where n is the number of nodes. The space complexity arises from the queue used for level-order traversal.

Applications

• Useful in verifying binary tree properties, especially when implementing binary heap data structures.
• Can be used in hierarchical data representations where we want to ensure the completeness of the data structure.

Conclusion

The Check Completeness of a Binary Tree problem is an essential exercise for understanding tree traversal techniques like breadth-first search (BFS). By ensuring all levels are filled and that the nodes at the last level are as far left as possible, we can confirm if a binary tree is complete. This problem is a good way to practice BFS and understand the properties of binary trees.

Practice this problem to sharpen your skills in level-order traversal and tree completeness checking. It also builds the foundation for problems involving tree structures that require validation of their properties.