JavaScript Program to Check if a Binary Tree is Complete - Coding

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

Using Iteration

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.

Using Recursion

In this approach, we first count the number of nodes in the binary tree. Then, we recursively traverse the tree and check if the indices assigned to each node follow the complete binary tree property. If any node’s index is greater than or equal to the total number of nodes in the tree, the tree cannot be complete.

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

JavaScript

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

function countNodesFun(root) {
    if (!root) return 0;
    return 1 + countNodesFun(root.left) + 
                countNodesFun(root.right);
}

function ifCompleteBT(root, index, totalNodes) {
    if (!root) return true;
    if (index >= totalNodes) return false;
    return (ifCompleteBT(root.left, 2 * index + 1,
                                    totalNodes) &&
        ifCompleteBT(root.right, 2 * 
                            index + 2, totalNodes));
}

function isCompleteBT(root) {
    let totalNodes = countNodesFun(root);
    return ifCompleteBT(root, 0, totalNodes);
}

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?", 
                        isCompleteBT(root));

Output

Is the binary tree complete? true

Time Complexity: O(N) where N is the number of nodes in the tree.

Space Complexity: O(h) where h is the height of the given tree.

Reffered: https://www.geeksforgeeks.org

JavaScript

Related
JavaScript Program to Find the Rank of a Matrix
VueJS for backend developers
Segregate 0s and 1s using JavaScript
Javascript WeakRef.prototype.deref()
JavaScript Program to Check if all Leaf Nodes are at Same Level or Not

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	15