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

Maximum Width of Binary Tree

📖 Scenario: You are working on a program that analyzes the shape of a binary tree. The width of a binary tree at a certain level is the number of nodes between the leftmost and rightmost non-null nodes at that level, including null nodes in between. Your task is to find the maximum width among all levels of the tree.

🎯 Goal: Build a TypeScript program that calculates the maximum width of a given binary tree using level order traversal and indexing nodes to account for null gaps.

📋 What You'll Learn

Create a binary tree node class called TreeNode with val, left, and right properties

Create a sample binary tree with the exact structure specified

Create a variable called maxWidth initialized to 0

Use a queue to perform level order traversal with node indices

Calculate the width at each level and update maxWidth

Print the final maxWidth value

💡 Why This Matters

🌍 Real World

Calculating the maximum width of a binary tree is useful in scenarios like network topology analysis, organizational charts, and understanding data structures in memory.

💼 Career

This concept is important for software engineers working with tree data structures, optimizing algorithms, and preparing for technical interviews.

1

Create the Binary Tree Structure

Create a class called TreeNode with a constructor that takes a number val and initializes left and right to null. Then create the following binary tree by creating nodes and linking them:

Root node with value 1
Root's left child with value 3
Root's right child with value 2
Node 3's left child with value 5
Node 3's right child with value 3
Node 2's right child with value 9

DSA Typescript

// Define TreeNode class and create the tree nodes
// Your code here

Hint

Start by defining the TreeNode class with val, left, and right. Then create the nodes exactly as described and link them to form the tree.

2

Initialize Maximum Width Variable

Create a variable called maxWidth and set it to 0. This will keep track of the maximum width found so far.

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number) {
        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.right = new TreeNode(9);

// Create maxWidth variable
// Your code here

Hint

Just create a variable maxWidth and set it to zero to start counting the maximum width.

3

Calculate Maximum Width Using Level Order Traversal

Use a queue to perform level order traversal of the tree. Store pairs of node and its index starting with root and index 0. For each level, find the width by subtracting the first index from the last index and adding 1. Update maxWidth if the current width is larger. Add children to the queue with their corresponding indices (2 * index for left child, 2 * index + 1 for right child).

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number) {
        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.right = new TreeNode(9);

let maxWidth = 0;

// Perform level order traversal and update maxWidth
// Your code here

Hint

Use a queue to keep track of nodes and their indices. For each level, calculate the width and update maxWidth. Add children with updated indices to the queue.

4

Print the Maximum Width

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

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number) {
        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.right = new TreeNode(9);

let maxWidth = 0;

const queue: Array = [[root, 0]];

while (queue.length > 0) {
    const levelLength = queue.length;
    const levelIndices = queue.map(pair => pair[1]);
    const levelMin = levelIndices[0];
    const levelMax = levelIndices[levelIndices.length - 1];
    const width = levelMax - levelMin + 1;
    if (width > maxWidth) {
        maxWidth = width;
    }

    for (let i = 0; i < levelLength; i++) {
        const [node, index] = queue.shift()!;
        if (node.left !== null) {
            queue.push([node.left, 2 * index]);
        }
        if (node.right !== null) {
            queue.push([node.right, 2 * index + 1]);
        }
    }
}

// Print maxWidth
// Your code here

Hint

Use console.log(maxWidth) to display the maximum width after the traversal.