Today’s Leetcode July Challenge problem is a neat little binary tree variation. The problem presents us with the root of a binary tree and asks us to return that tree’s maximum width. The maximum width here is defined as the maximum number of nodes between the leftmost and rightmost nodes of a single level in the tree. The problem description is a little confusing, but a simple example clears things up. Let’s look at a potential input tree–node values are omitted as they have no bearing on this problem.

Input:
graph TD; 1((x)) --- 2((x)) 1((x)) --- 3((x)) 2((x)) --- 4((x)) 2((x)) --- 5((x)) 3((x)) --- null 3((x)) --- 6((x))
Max Width = 4

Looking at this representation, it’s pretty easy to operationalize for any given node, $n$, its level ordered position value, $op_n$. For any left child node, $op_n = 2\cdot op_{parentnode_n}\;$, and for any right child node $op_n = 2\cdot op_{parentnode_n}+1$. Using this method, as opposed more intuitively counting nodes in a level order traversal, we can account for null nodes between the leftmost and rightmost nodes in a given level.

graph TD; 1((1)) --- 2((2)) 1((1)) --- 3((3)) 2((2)) --- 4((4)) 2((2)) --- 5((5)) 3((3)) --- null 3((3)) --- 6((7))
This looks like a good approach, so now we just need to do a slightly modified level order traversal wherein each node is stored with its ordered position in a queue. We can use those paired values to calculate the ordered position of each node’s child nodes as well as to calculate the width of each level. That calculation becomes very convenient upon the realization that the traversal queue will contain all the nodes of a given level, ordered from left to right, at the beginning of that level’s traversal. We’ll just take that opportunity to compare the current maximum width to the distance between the first and last node in the queue.

int widthOfBinaryTree(TreeNode* root) {
   if(!root) return 0;

   int maxWidth = 0;
   // store the each node with its ordered position as a pair, could also make a struct
   //	to associate the values, but seems unecessary here.
   queue<pair<TreeNode*,unsigned long long>> q;
   q.push({root, 1});
   while(!q.empty()) {
	  // add 1 to the distance between the nodes to get the inclusive width.
	  //	have to cast width difference to int for comparison with maxWidth.
	  maxWidth = max(maxWidth, (int)(q.back().second - q.front().second) + 1);

	  int levelSize = q.size();
	  for(int i=0;i<levelSize;i++) {
		 auto [node, position] = q.front();
		 q.pop();

		 // the other option to handle integer overflow would be cast position to a long and
		 //	allow an implicit cast back to int, which would likely truncate the highest
		 //	significant digits, but is compliler dependent and undefined behaviour.
		 if(node->left) q.push({node->left, position*2});
		 if(node->right) q.push({node->right, position*2+1});
	  }
   }
   return maxWidth;
}

That was a fun little problem with a touch of edge case wrangling that you can see in the code comments above. Check back tomorrow to see another problem!