Maximum Width of Binary Tree

Intuition

We could DFS or BFS to traverse the tree and mark the position for each node. For each node, its left node is the same position at itself and its right node is in its position plus 1.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        left_most = []
        right_most = []
        self._dfs(root, 0, 0, left_most, right_most)
        return max([j - i + 1 for i, j in zip(left_most, right_most)])

    def _dfs(self, node, depth, shift, left_most, right_most):
        if node is None:
            return
        if depth >= len(left_most):
            left_most.append(shift)
            right_most.append(shift)
        else:
            right_most[depth] = shift
        self._dfs(node.left, depth + 1, shift * 2, left_most, right_most)
        self._dfs(node.right, depth + 1, shift * 2 + 1, left_most, right_most)