662. Maximum Width of Binary Tree - Explanation

Problem Link



Intuition

The width of a level is defined by the distance between the leftmost and rightmost non-null nodes, including any null nodes in between. To measure this, we assign each node a position number: the root is 1, and for any node at position p, its left child is at 2 * p and right child at 2 * p + 1. Using BFS, we traverse level by level and compute the width as the difference between the last and first position on each level, plus one.

Algorithm

  1. Initialize res = 0 and a queue with (root, 1, 0) representing (node, position, level).
  2. Track prevLevel and prevNum to record the first position on each level.
  3. While the queue is not empty:
    • Dequeue (node, num, level).
    • If level > prevLevel, update prevLevel and prevNum to the current level and position.
    • Update res = max(res, num - prevNum + 1).
    • Enqueue the left child with position 2 * num and the right child with 2 * num + 1, both at level + 1.
  4. Return res.
# 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:
        res = 0
        q = deque([(root, 1, 0)])  # [node, num, level]
        prevLevel, prevNum = 0, 1

        while q:
            node, num, level = q.popleft()

            if level > prevLevel:
                prevLevel = level
                prevNum = num

            res = max(res, num - prevNum + 1)
            if node.left:
                q.append((node.left, 2 * num, level + 1))
            if node.right:
                q.append((node.right, 2 * num + 1, level + 1))

        return res

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

2. Breadth First Search (Optimal)

Intuition

Position numbers can grow large in deep skewed trees, potentially causing overflow. To prevent this, we normalize positions at each level by subtracting the starting position of that level. This keeps the numbers small while still correctly computing the width as the difference between the rightmost and leftmost positions on each level.

Algorithm

  1. Initialize res = 0 and a queue with (root, 0).
  2. While the queue is not empty:
    • Record start as the position of the first node in the current level.
    • For each node in the current level:
      • Compute curNum = num - start to normalize.
      • Update res = max(res, curNum + 1).
      • Enqueue children with positions 2 * curNum and 2 * curNum + 1.
  3. Return res.
# 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:
        res = 0
        q = deque([(root, 0)])

        while q:
            start = q[0][1]
            for _ in range(len(q)):
                node, num = q.popleft()
                curNum = num - start
                res = max(res, curNum + 1)
                if node.left:
                    q.append((node.left, 2 * curNum))
                if node.right:
                    q.append((node.right, 2 * curNum + 1))

        return res

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

Intuition

We can also solve this with DFS by recording the first position encountered at each level. As we traverse, whenever we visit a node, we check if its level has been seen before. If not, we record its position as the first for that level. The width at any node is computed as the difference from the first position on its level. We normalize child positions to avoid overflow.

Algorithm

  1. Maintain a map first where first[level] stores the position of the first node visited at that level.
  2. Define dfs(node, level, curNum):
    • If node is null, return.
    • If level not in first, set first[level] = curNum.
    • Update res = max(res, curNum - first[level] + 1).
    • Recurse on left child with level + 1 and position 2 * (curNum - first[level]).
    • Recurse on right child with level + 1 and position 2 * (curNum - first[level]) + 1.
  3. Call dfs(root, 0, 0) and return res.
# 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:
        first = {}
        res = 0

        def dfs(node, level, num):
            nonlocal res
            if not node:
                return

            if level not in first:
                first[level] = num

            res = max(res, num - first[level] + 1)
            dfs(node.left, level + 1, 2 * num)
            dfs(node.right, level + 1, 2 * num + 1)

        dfs(root, 0, 0)
        return res

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

Common Pitfalls

Integer Overflow from Position Numbers

Position numbers double at each level (2 * num for left child, 2 * num + 1 for right). In a deep, skewed tree, these values can overflow standard integer types. Use larger types like unsigned long long in C++ or BigInt in JavaScript, or normalize positions by subtracting the starting position at each level.

Miscounting the Width

Width is defined as the number of nodes between the leftmost and rightmost positions on a level, inclusive. The formula is rightmost - leftmost + 1, not just the difference. Forgetting the + 1 gives a width that is one less than correct.

Incorrect Level Tracking in BFS

When processing nodes level by level, you must correctly identify the first node of each new level to record its starting position. If you mix up the level boundaries or fail to update the starting position when entering a new level, the width calculation will be incorrect.