LeetCode 958: Check Completeness of a Binary Tree Solution

Master LeetCode problem 958 (Check Completeness of a Binary Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

958. Check Completeness of a Binary Tree

Medium

Tree Breadth-First Search Binary Tree

Problem Explanation

Explanation:

To determine if a binary tree is a complete binary tree, we can perform a level-order traversal of the tree and monitor if we encounter any null node after seeing a non-null node. In a complete binary tree, all null nodes should appear after all non-null nodes at the same level.

Algorithm:

Perform a level-order traversal of the binary tree using a queue.
For each node encountered:
- If the node is null, set a flag indicating that null nodes have been encountered.
- If the flag indicating null nodes have been encountered is set, and the current node is not null, return false.
If we finish the traversal without encountering the condition in step 2, return true.

Time Complexity:

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree.

Space Complexity:

The space complexity of this algorithm is O(n), where n is the number of nodes in the binary tree.

: :

Solution Code

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

class Solution {
    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean nullNodeEncountered = false;

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

        return true;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 958 (Check Completeness of a Binary Tree)?

This page provides optimized solutions for LeetCode problem 958 (Check Completeness of a Binary Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 958 (Check Completeness of a Binary Tree)?

The time complexity for LeetCode 958 (Check Completeness of a Binary Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 958 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 958 in Java, C++, or Python.

Back to LeetCode Solutions