algoadvance

Leetcode 662. Maximum Width of 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 one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes are also counted into the length calculation.

The binary tree can have a maximum height of 1000 and a maximum number of nodes as 3000.

Clarifying Questions

  1. How are the null nodes between the end-nodes treated in the width calculation?
    • Null nodes are included in the width calculation.
  2. Can the tree have null nodes at intermediate levels?
    • Yes, the tree can have null nodes at intermediate levels.

Strategy

  1. We can perform a level-order traversal (BFS) to examine each level of the tree.
  2. During the traversal, we can keep track of node positions to calculate the width.
  3. For each level, note the position (index) of the leftmost and rightmost non-null nodes.
  4. Calculate the width at each level using these positions and keep track of the maximum width found.

Code

#include <iostream>
#include <queue>
#include <utility>
#include <limits.h>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if (!root) return 0;

        // Queue will store pairs of TreeNode* and its position index
        queue<pair<TreeNode*, unsigned long long>> q;
        q.push({root, 0});

        unsigned long long maxWidth = 0;

        while (!q.empty()) {
            int size = q.size();
            unsigned long long minIndex = q.front().second;
            unsigned long long first, last;

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

                if (i == 0) first = curIndex;
                if (i == size - 1) last = curIndex;

                if (node->left) q.push({node->left, 2 * curIndex + 1});
                if (node->right) q.push({node->right, 2 * curIndex + 2});
            }

            maxWidth = max(maxWidth, last - first + 1);
        }

        return maxWidth;
    }
};

Strategy Explanation

  1. Initialization: Use a queue to facilitate level-order traversal, where each element in the queue is a pair consisting of a tree node and its corresponding position index.
  2. Traversal and Width Calculation:
    • For each level, determine the leftmost and rightmost indices.
    • Normalize indices by subtracting the minimum index of the current level to avoid overflow (since indices can become very large).
    • Calculate the width of the current level as last - first + 1 and keep updating the maximum width.
  3. Return the maximum width found during the traversal.

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI