Maximum Width of Binary Tree

How it works

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.

Steps

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.

Complexity

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

Things to watch for

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.

from typing import Optional

# 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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    unordered_map<int, unsigned long long> first;

public:
    int widthOfBinaryTree(TreeNode* root) {
        unsigned long long res = 0;

        dfs(root, 0, 0, res);
        return int(res);
    }

private:
    void dfs(TreeNode* node, int level, unsigned long long num, unsigned long long& res) {
        if (!node) {
            return;
        }

        if (!first.count(level)) {
            first[level] = num;
        }

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