How to use Iteration In Javascript
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.
// 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:
Below are the approaches to check if a binary tree is complete using JavaScript:
Table of Content
- Using Iteration
- Using Recursion