Maximum Width of a Binary Tree

Problem Statement

Given the root of a binary tree, return the maximum width of the given tree.

The maximum width of a tree is the maximum width among all levels. The width of a level is determined by measuring the distance between its end nodes, which are the leftmost and rightmost non-null nodes. The length calculation additionally takes into account the null nodes that would be present between the end nodes if a full binary tree were to stretch down to that level.

Examples

Example 1:

Input:
        1
       / \
      3   2
     /     \
    5       9
   / \     /
  6   7   10
Output: 8


Explanation:
Level 1: [1] → Width = 1
Level 2: [3, 2] → Width = 2
Level 3: [5, null, null, 9] → Width = 4
Level 4: [6, 7, null, null, null, null, 10] → Width = 8
Maximum Width = 8.

Example 2:

Input:
        1
       / \
      3   2
     /
    5
Output: 2

Explanation:
Level 1: [1] → Width = 1
Level 2: [3, 2] → Width = 2
Level 3: [5, null] → Width = 2
Maximum Width = 2.

Example 3:

Input:
        1
       /
      3
     /
    5
Output: 1

Explanation:
Level 1: [1] → Width = 1
Level 2: [3] → Width = 1
Level 3: [5] → Width = 1
Maximum Width = 1.

Example 4:

Input:
        1
       / \
      2   3
         / \
        4   5
Output: 4

Explanation:
Level 1: [1] → Width = 1
Level 2: [2, 3] → Width = 2
Level 3: [null, null, 4, 5] → Width = 4
Maximum Width = 4.

Different Approaches

1️⃣ Level Ordre Traversal

Intuition:

To compute the maximum width:

1. Perform a level-order traversal (using a queue).
2. Use a positional index for nodes, treating the tree as a complete binary tree:
   • For a node at position i, its left child is at 2*i, and its right child is at 2*i + 1.
3. For each level:
   • Record the minimum and maximum indices at that level.
   • Compute the width as maxIndex - minIndex + 1.

Approach:

1. Use a queue to store nodes along with their positional indices.
2. At each level:
   • Traverse all nodes in the level.
   • Calculate the width using the first and last node's indices.
   • Push the left and right children (if present) into the queue with updated indices.
3. Track the maximum width across all levels.

Code:

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

// Definition for a binary tree node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if (!root) return 0; // If the tree is empty, the width is 0.

        int maxWidth = 0; // Variable to track the maximum width of the tree.
        queue<pair<TreeNode*, unsigned long long>> q; // Queue to store nodes along with their positional index.
        q.push({root, 0}); // Start with the root node at index 0.

        while (!q.empty()) {
            int levelSize = q.size(); // Number of nodes at the current level.
            unsigned long long minIndex = q.front().second; // Minimum index of the current level for normalization.
            unsigned long long first, last; // Variables to store the first and last indices of the current level.

            for (int i = 0; i < levelSize; ++i) {
                TreeNode* node = q.front().first; // Current node.
                unsigned long long index = q.front().second - minIndex; // Normalize index to avoid overflow.
                q.pop();

                if (i == 0) first = index; // Set the first index for the level.
                if (i == levelSize - 1) last = index; // Set the last index for the level.

                // Push the left child to the queue with its positional index.
                if (node->left) q.push({node->left, 2 * index});
                // Push the right child to the queue with its positional index.
                if (node->right) q.push({node->right, 2 * index + 1});
            }

            // Calculate the width of the current level and update the maximum width.
            maxWidth = max(maxWidth, int(last - first + 1));
        }

        return maxWidth; // Return the maximum width of the tree.
    }
};

// Helper function to build a tree for testing
TreeNode* buildTree() {
    TreeNode* root = new TreeNode(1); // Root node.
    root->left = new TreeNode(3); // Left child of the root.
    root->right = new TreeNode(2); // Right child of the root.
    root->left->left = new TreeNode(5); // Left child of node 3.
    root->right->right = new TreeNode(9); // Right child of node 2.
    root->left->left->left = new TreeNode(6); // Left child of node 5.
    root->left->left->right = new TreeNode(7); // Right child of node 5.
    root->right->right->left = new TreeNode(10); // Left child of node 9.
    return root; // Return the constructed tree.
}

// Main function
int main() {
    Solution sol; // Create a solution object.
    TreeNode* root = buildTree(); // Build the tree for testing.
    cout << "Maximum Width: " << sol.widthOfBinaryTree(root) << endl; // Calculate and display the maximum width.
    return 0; // End of the program.
}

Complexity Analysis:

• Time Complexity: O(N)
  • As each node is visited once, so the time complexity if O(N), where N is the number of nodes.
• Space Complexity: O(W)
  • The queue stores at most one level of nodes. In the worst case (a complete binary tree), the queue size if O(W), where W is the maximum width of the tree.
  • W = O(N)
  • Overall Space Complexity: O(W)