# 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:
        min_level = defaultdict(lambda: float('inf'))
        max_level = defaultdict(lambda: -float('inf'))

        def dfs(node: Optional[TreeNode], pos: int = 0, level: int = 0):
            if node is None:
                return

            min_level[level] = min(min_level[level], pos)
            max_level[level] = max(max_level[level], pos)
            dfs(node.left, pos * 2, level + 1)
            dfs(node.right, pos * 2 + 1, level + 1)
        dfs(root)

        ans = 0
        for level in min_level.keys():
            ans = max(ans, max_level[level] - min_level[level] + 1)
        return ans