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