DAY 59 - Maximum Width of Binary Tree

Welcome to DAY 59. Today we will diverge once again into the Data Structure Trees and look at some more questions. I suggest reading the previous articles that I have written on Trees before reading this.

Question: Maximum Width of Binary Tree

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 that would be present in a complete binary tree extending down to that level are also counted into the length calculation.

It is guaranteed that the answer will in the range of a 32-bit signed integer.

Example 1:

• Input: root = [1,3,2,5,3,null,9]
• Output: 4
• Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).

Intuition:

• First of all, we need to understand the meaning of width at a level clearly. In the example image we can see it's the rightmost and leftmost node in the left and right subtrees at the best.
• Therefore we can use a level order traversal to traverse the tree and in every level, we try to find the leftmost and rightmost node of that level.
• To achieve this we would need a proper indexing strategy to uniquely index nodes of a level. Once we know the leftMost and rightMost nodes, width can be defined as (rightMost- leftMost +1).

• If we index the tree we can easily calculate the width of the tree as rightMostNode – leftMostNode +1. Then we can return the maximum width as our answer. To store the index, we can use a pair of values in our queue( that we use for level order traversal).

• If we are at index i, then its left and right child are(in 0-based indexing): 2*i+1 and 2*i+2 respectively. Please note that NULL nodes are not hampering the indexing in any way.

Algorithm and Code:

Algorithm:

• The widthOfBinaryTree function takes the root of a binary tree as input and returns an integer representing the maximum width of the tree.
• If the root is nullptr (i.e., the tree is empty), the function returns 0 as there are no nodes in the tree.
• The function initializes a variable ans to 0, which will store the maximum width.
• It uses a queue of pairs, where each pair contains a TreeNode pointer and its corresponding index value.
• The algorithm starts by pushing the root node into the queue with its index value as 0.
• While the queue is not empty, the algorithm processes each level of the tree:
• a. It retrieves the number of nodes in the current level (size) and initializes two variables: curMin to store the index of the leftmost node in the current level, and leftMost and rightMost to keep track of the index values of the leftmost and rightmost nodes in the current level.
• b. The algorithm processes each node in the current level by dequeuing it from the queue.
• c. It calculates the current index value (cur_id) of the node by subtracting curMin from the index value obtained from the queue. This step is performed to prevent integer overflow.
• d. The algorithm updates the leftMost and rightMost variables. If it's the first node in the current level (i.e., i == 0), it sets leftMost to cur_id, and if it's the last node in the current level (i.e., i == size - 1), it sets rightMost to cur_id.
• e. For each dequeued node, the algorithm enqueues its left and right children into the queue with their updated index values. The index value of the left child is calculated as cur_id * 2 + 1, and the index value of the right child is calculated as cur_id * 2 + 2.
• After processing each level, the algorithm calculates the width of the current level as (rightMost - leftMost + 1) and updates the ans variable to store the maximum width seen so far.
• Once the BFS traversal is complete, the function returns the maximum width stored in the ans variable as the output.

Code:

/**
 * Definition for a binary tree node.
 * 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;
  int ans = 0;
  queue < pair < TreeNode * , int >> q;
  q.push({
    root,
    0
  });
  while (!q.empty()) {
    int size = q.size();
    long long curMin = q.front().second;
    int leftMost, rightMost;
    for (int i = 0; i < size; i++) {
      long long cur_id = q.front().second - curMin; // subtracted to prevent integer overflow
      TreeNode * temp = q.front().first;
      q.pop();
      if (i == 0) leftMost = cur_id;
      if (i == size - 1) rightMost = cur_id;
      if (temp -> left)
        q.push({
          temp -> left,
          cur_id * 2 + 1
        });
      if (temp -> right)
        q.push({
          temp -> right,
          cur_id * 2 + 2
        });
    }
    ans = max(ans, rightMost - leftMost + 1);
  }
  return ans;
}
};

Complexity Analysis:

• Time: O(N)
• Space: O(N)

Thanks for reading. Feedback is highly appreciated!