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

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: 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`

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