LC 0662 [M] Maximum Width of Binary Tree - ALawliet/algorithms GitHub Wiki

We know that a binary tree can be represented by an array (assume the root begins from the position with index 1 in the array). If the index of a node is i, the indices of its two children are 2i and 2i + 1. The idea is to use two arrays (start[] and end[]) to record the the indices of the leftmost node and rightmost node in each level, respectively. For each level of the tree, the width is end[level] - start[level] + 1. Then, we just need to find the maximum width.

# 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:  
        max_width = 0
        Q = deque([ (root, 1) ]) # node, i (index of this node if this binary tree were represented as an array so it includes nulls)

        while Q:
            end_level = Q[-1][1]
            start_level = Q[0][1]
            width_level = end_level - start_level + 1
            max_width = max(max_width, width_level)
            
            for _ in range(len(Q)):
                node, i = Q.popleft()
                # print(node.val, i)
                
                if node.left:
                    Q.append( (node.left, 2*i) )
                if node.right:
                    Q.append( (node.right, 2*i + 1) )
                    
        return max_width