# LeetCode ANSWER FOR 958. Check Completeness of a Binary Tree #LEARN HOW TO CODE

958. 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`

.

Example 1:

Input:root = [1,2,3,4,5,6]Output:trueExplanation: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:falseExplanation: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`

SOLUTION:

To check the completeness of a binary tree, you can use a breadth-first search algorithm (BFS). Here's an example implementation in JavaScript:

function isCompleteTree(root) { if (!root) return true; const queue = [root]; let nullFound = false; while (queue.length) { const node = queue.shift(); // If we've already found a null node, and we're not at the end of the tree, then the tree is not complete if (nullFound && node) { return false; } // If we find a null node, mark that we've found one if (!node) { nullFound = true; } else { // Otherwise, add its children to the queue queue.push(node.left); queue.push(node.right); } } // If we've made it this far, then the tree is complete return true; }

This function takes in the root node of a binary tree, and returns `true`

if the tree is complete, and `false`

otherwise.

The function starts by checking if the root node is null. If it is, then the tree is trivially complete, so we return `true`

.

Next, we initialize a queue with the root node, and a flag `nullFound`

to keep track of whether we've found a null node yet.

We then enter into a loop that continues until the queue is empty. At each iteration of the loop, we remove the next node from the queue.

If we've already found a null node, and we encounter a non-null node, then the tree is not complete, so we return `false`

.

If we encounter a null node, we set the `nullFound`

flag to `true`

.

If we encounter a non-null node, we add its left and right children to the queue.

After we've processed all the nodes in the tree, if we haven't found a non-null node following a null node, then the tree is complete, and we return `true`

.

## Post a Comment