Leetcode 662 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 are also counted into the length calculation.

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

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

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

• Let us assign an id to each node, similar to the index of a heap. root is 1, left child = parent * 2, right child = parent * 2 + 1. Width = id(right most child) – id(left most child) + 1, so far so good. However, this kind of id system grows exponentially, it overflows even with long type with just 64 levels. To avoid that, we can remap the id with id – id(left most child of each level).

# 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: TreeNode) -> int:
    ids = []
    def dfs(node: TreeNode, d: int, id: int) -> int:
      if not node: return 0
      if d == len(ids): ids.append(id)
      return max(id - ids[d] + 1, 
                 dfs(node.left, d + 1, (id - ids[d]) * 2),
                 dfs(node.right, d + 1, (id - ids[d]) * 2 + 1))
    return dfs(root, 0, 0)