maximum-width-of-binary-tree.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        '''
         {
            1 : [1],
            2 : [3, 2]
            3 : [5, none, none, 9]
            4 : [6, none, none, none, none, none, 7]
         }
        '''
        
        queue = deque([(0, 1, root)])
        min_max_array = []
        
        while queue:
            level, index, node = queue.popleft()
            if not node:
                continue
            if (len(min_max_array) == level):
                min_max_array.append((float('inf'), float('-inf')))
            min_max_array[level] = (min(min_max_array[level][0], index), max(min_max_array[level][1], index)) 
            queue.append((level + 1, index * 2, node.left))
            queue.append((level + 1, (index * 2) + 1, node.right))
        
        max_width = 1
        
        for min_val, max_val in min_max_array:
            max_width = max(max_val - min_val + 1, max_width)
            
        return max_width