Skip to main content

Maximum Width of Binary Tree

Question​

What is the maximum width of a given binary tree?

Example 1
None

Solution​

all//Maximum Width of Binary Tree.py

from collections import deque
# 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):
        if root is None:
            return 0

        max_width = 0
        queue = deque([(root, 0, 0)])

        while queue:
            node, depth, position = queue.popleft()
            if depth == 0:
                leftmost = position
            max_width = max(max_width, position - leftmost + 1)
            if node.left is not None:
                queue.append((node.left, depth+1, 2*position))
            if node.right is not None:
                queue.append((node.right, depth+1, 2*position + 1))

        return max_width