How to use Iteration In Javascript

Using Recursion

In this approach, we traverse the binary tree level by level using a queue. At each level, we check if there are any missing nodes before any non-null node. If we encounter a node with one child while there are still nodes with two children, the tree cannot be complete. Similarly, if we encounter a node with no children or only a left child, all the following nodes should also have no children. If any violation of these conditions is found during traversal, we return false otherwise the tree is complete.

Example: The example below checks if a binary tree is complete Using Iteration.

JavaScript

// Define a class for a tree node
class TreeNode {
    constructor(value) {
        this.val = value;
        this.left = null;
        this.right = null;
    }
}

// Function to check binary tree is complete iteratively
function ifComBTree(root) {
    if (!root) return true;
    let queueVariable = [root];
    let foundNull = false;

    while (queueVariable.length > 0) {
        let node = queueVariable.shift();
        if (!node) {
            foundNull = true;
            continue;
        }

        if (foundNull) return false;
        queueVariable.push(node.left);
        queueVariable.push(node.right);
    }

    return true;
}

let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

console.log("Is the binary tree complete?", 
                        ifComBTree(root));

Output

Is the binary tree complete? true

Time Complexity: O(n) where n is the number of nodes in a given Binary Tree.

Auxiliary Space: O(h) where h is the height of the given Binary Tree.

JavaScript Program to Check if a Binary Tree is Complete

Given a Binary Tree, Our task is to check whether the given Binary Tree is a Complete Binary Tree or not in JavaScript. A complete binary tree is one where every level is filled except possibly the last level and all nodes are positioned as far to the left as possible.

Example: Below the tree is a Complete Binary Tree:

Complete Binary Tree

Below are the approaches to check if a binary tree is complete using JavaScript:

Table of Content

Using Iteration
Using Recursion

Tags:

#JavaScript-Program #JavaScript #Web Technologies

Using Recursion

How to use Iteration In Javascript

JavaScript Program to Check if a Binary Tree is Complete

Similar Reads

Contact Us