Maximum Width of Binary Tree in DSA C++ - Build from Scratch

Maximum Width of Binary Tree

📖 Scenario: Imagine you are working with a family tree app that shows generations of family members. You want to find out the widest generation -- the one with the most members lined up horizontally.

🎯 Goal: Build a program that calculates the maximum width of a binary tree. The width is the number of nodes between the leftmost and rightmost non-null nodes at any level, including nulls in between.

📋 What You'll Learn

Create a binary tree node structure with integer values

Build a sample binary tree with given nodes

Use a breadth-first search approach with position indexing

Calculate the maximum width of the tree

Print the maximum width as the final output

💡 Why This Matters

🌍 Real World

Calculating the maximum width of a binary tree helps in understanding the breadth of hierarchical data, such as family trees, organizational charts, or file directory structures.

💼 Career

This concept is useful for software engineers working on tree data structures, UI layout engines, and algorithms that require breadth analysis of hierarchical data.

1

Create the Binary Tree Node Structure and Sample Tree

Create a struct called TreeNode with an int val, and two pointers left and right to TreeNode. Then create a binary tree with root node value 1, root's left child value 3, root's right child value 2, root's left child's left child value 5, and root's left child's right child value 3.

DSA C++

// Your code here to define TreeNode and create the tree

Hint

Define a struct with a constructor for easy node creation. Then link nodes to form the tree.

2

Add a Queue and Position Indexing Setup

Include the queue and utility headers. Create a queue of pairs called q that stores TreeNode* and unsigned long long for position indexing. Push the root node with position 0 into q.

DSA C++

#include 
#include 

// Your code here to create queue and push root with position 0

Hint

Use a queue to hold nodes with their horizontal positions starting at 0 for the root.

3

Calculate the Maximum Width Using Level Order Traversal

Write a while loop that runs while q is not empty. Inside, get the size of q as level_size. Store the position of the first node in the level as level_head_index. Iterate level_size times, popping from q. For each node, get its position pos and normalize it by subtracting level_head_index. If the node has a left child, push it with position 2 * pos + 1. If the node has a right child, push it with position 2 * pos + 2. Track the last node's normalized position as level_tail_index. Update an integer variable max_width with the maximum of itself and level_tail_index - level_head_index + 1. Initialize max_width to 0 before the loop.

DSA C++

int max_width = 0;
// Your code here to calculate max_width using level order traversal

Hint

Use a queue to traverse level by level. Normalize positions to avoid overflow. Update max_width with the width of each level.

4

Print the Maximum Width

Add a cout statement to print the value of max_width followed by a newline.

DSA C++

cout << max_width << endl;  // Print the maximum width

Hint

Print the final maximum width after processing all levels.