Maximum Width of Binary Tree

Written by: Tushar Sharma

Featured image for Maximum Width of Binary Tree

The problem statement, as given on LeetCode, asks us to find the maximum width of a binary tree. The width of a level is defined as the number of nodes at that level. The maximum width of the binary tree is the maximum width among all levels.

Solution

python
java

Code Walkthrough

Initialization: Start with the root node of the binary tree. Initialize a queue to hold nodes and their positions. Set a variable max_width to keep track of the maximum width seen so far (initially set to 0).

Breadth-First Search (BFS): Perform a BFS traversal of the binary tree. Begin with the root node and assign it a position of 0. Enqueue the root node along with its position into the queue.

While the Queue is not Empty:

Get the size of the queue, which represents the number of nodes at the current level.
Initialize left_index and right_index to track the indices of the leftmost and rightmost nodes at the current level.
Iterate through the nodes at the current level:
Dequeue a node and its position from the queue.
Update left_index with the position of the leftmost node.
Update right_index with the position of the last node (rightmost) in the current level.
Calculate the width of the current level as right_index - left_index + 1.
Update max_width with the maximum of its current value and the width of the current level.
If the node has a left child, enqueue the left child with a position calculated as (2 * current_position) + 1.
If the node has a right child, enqueue the right child with a position calculated as (2 * current_position) + 2.
Return max_width: After processing all levels, max_width will hold the maximum width of the binary tree.

Time Complexity

The time complexity is O(N), where N is the number of nodes in the binary tree. This is because both solutions traverse all nodes in the tree once using BFS.