Maximum Width of Binary Tree in DSA Javascript - Build from Scratch

Maximum Width of Binary Tree

📖 Scenario: You are working on a program that analyzes the structure of a binary tree. The goal is to find the maximum width of the tree, which means the largest number of nodes present at any single level.Imagine the tree as a family tree where each generation is a level. You want to find the generation with the most family members.

🎯 Goal: Build a JavaScript program that calculates the maximum width of a given binary tree. You will create the tree nodes, set up a queue for level order traversal, calculate the width at each level, and finally print the maximum width.

📋 What You'll Learn

Create a binary tree using nodes with val, left, and right properties

Use a queue to perform level order traversal

Calculate the width of each level by counting nodes

Find and print the maximum width among all levels

💡 Why This Matters

🌍 Real World

Finding the maximum width of a binary tree helps in understanding the structure and balance of hierarchical data, such as organizational charts or file systems.

💼 Career

This concept is useful for software engineers working with tree data structures, optimizing algorithms, and solving problems related to data organization and traversal.

1

Create the Binary Tree Nodes

Create a class called TreeNode with a constructor that takes val and sets this.val, this.left, and this.right to null. Then create a binary tree with root node value 1, root's left child value 3, root's right child value 2, left child's left child value 5, left child's right child value 3, and right child's left child value 4.

DSA Javascript

# Your code here

Hint

Define the TreeNode class first, then create the nodes and link them as described.

2

Set Up a Queue for Level Order Traversal

Create a variable called queue and initialize it as an array containing the root node. Also create a variable called maxWidth and set it to 0 to keep track of the maximum width found.

DSA Javascript

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

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

// Initialize queue and maxWidth
# Your code here

Hint

Use an array to hold nodes for level order traversal and a variable to track the maximum width.

3

Calculate Maximum Width Using Level Order Traversal

Use a while loop that runs as long as queue.length is greater than 0. Inside the loop, create a variable levelLength set to queue.length. Update maxWidth to be the maximum of maxWidth and levelLength. Then use a for loop from 0 to levelLength - 1 to remove the first node from queue and add its left and right children to queue if they exist.

DSA Javascript

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

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

const queue = [root];
let maxWidth = 0;

// Calculate maxWidth using level order traversal
# Your code here

Hint

Use a queue to process each level, update maxWidth, and add children nodes for the next level.

4

Print the Maximum Width

Write a console.log statement to print the value of maxWidth.

DSA Javascript

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

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

const queue = [root];
let maxWidth = 0;

while (queue.length > 0) {
    const levelLength = queue.length;
    maxWidth = Math.max(maxWidth, levelLength);
    for (let i = 0; i < levelLength; i++) {
        const node = queue.shift();
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
}

// Print the maximum width
# Your code here

Hint

Use console.log(maxWidth) to display the final answer.