Level order Traversal using a queue

Using Breadth-First Search

The level order traversal of the binary tree can be used to find the maximum width of the binary tree using the level order traversal of a binary tree. Perform the level order traversal using a queue. We calculate the maximum width of a binary tree. Keep the count of nodes at each level stored in the queue which will return the maximum width of a binary tree. Return the maximum width of a binary tree.

Example: In this queue is used to traverse each level of the binary tree using the queue data structure. At each level, we update the maximum width of a binary tree. Lastly, we return the maximum width of the binary tree stored in the variable after completing the whole traversal of a binary tree.

Javascript

class Node {
    constructor(key) {
        this.data = key;
        this.left = null;
        this.right = null;
    }
}
 
function maxWidth(root) {
    if (root === null) {
        return 0;
    }
 
    let maxWidth = 0;
    let queue = [];
    queue.push(root);
 
    while (queue.length > 0) {
        let count = queue.length;
        maxWidth = Math.max(maxWidth, count);
 
        while (count > 0) {
            let node = queue.shift();
 
            if (node.left) {
                queue.push(node.left);
            }
            if (node.right) {
                queue.push(node.right);
            }
 
            count--;
        }
    }
 
    return maxWidth;
}
 
// Example usage:
// Constructing a sample binary tree
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.right = new Node(8);
root.right.right.left = new Node(6);
root.right.right.right = new Node(7);
 
console.log("Maximum width of the binary tree:", maxWidth(root));

Output

Maximum width of the binary tree: 3

JavaScript Program to Find Maximum Width of Binary Tree

The maximum width of a given binary tree can be calculated by finding the maximum of all the level widths. The maximum width of a Binary tree is the maximum number of nodes present at any level. The maximum width of the Binary tree will include only the present node and not include null nodes.

The maximum width of a Binary Tree

In this example, we are going to see what is the maximum width of a binary tree. The maximum width of a binary tree is the maximum number of nodes present at any level. The maximum number of nodes present is returned as the maximum width of a binary tree.

Maximum Width

The maximum width at level 0 is 1.
The maximum width at level 1 is 2.
The maximum width at level 2 is 3.
The maximum width at level 3 is 3.

As the maximum width of the binary tree is 3 at level 2 and level 3. So the maximum width of a binary tree is 3.

There are several ways to find the maximum width of a Binary tree in JavaScript which are as follows:

Table of Content

Level order Traversal using a queue
Using Breadth-First Search

Tags:

#JavaScript Programs #JavaScript #Web Technologies

Using Breadth-First Search

Level order Traversal using a queue

Javascript

JavaScript Program to Find Maximum Width of Binary Tree

The maximum width of a Binary Tree

Similar Reads

Contact Us