Approach: BFS assigning heap-style indices; normalize per level

def widthOfBinaryTree(self, root):
    if not root: return 0
    best = 0; q = [(root, 0)]
    while q:
        first = q[0][1]; best = max(best, q[-1][1] - first + 1); nq = []
        for node, idx in q:
            p = idx - first
            if node.left: nq.append((node.left, p*2))
            if node.right: nq.append((node.right, p*2+1))
        q = nq
    return best

Complexity: O(n) time, O(w) space.

Full Solution — all languages

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 not root: return 0
        best = 0; q = [(root, 0)]
        while q:
            first = q[0][1]; best = max(best, q[-1][1] - first + 1); nq = []
            for node, idx in q:
                p = idx - first
                if node.left: nq.append((node.left, p * 2))
                if node.right: nq.append((node.right, p * 2 + 1))
            q = nq
        return best

import java.util.*;
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) {
        val = v;
    }
}
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        int best = 0;
        List<TreeNode> q = new ArrayList<>();
        List<Long> idx = new ArrayList<>();
        q.add(root);
        idx.add(0L);
        while (!q.isEmpty()) {
            long first = idx.get(0);
            best = Math.max(best, (int)(idx.get(idx.size() - 1) - first + 1));
            List<TreeNode> nq = new ArrayList<>();
            List<Long> ni = new ArrayList<>();
            for (int i = 0; i < q.size(); i++) {
                long p = idx.get(i) - first;
                TreeNode node = q.get(i);
                if (node.left != null) {
                    nq.add(node.left);
                    ni.add(p * 2);
                }
                if (node.right != null) {
                    nq.add(node.right);
                    ni.add(p * 2 + 1);
                }
            }
            q = nq;
            idx = ni;
        }
        return best;
    }
}

#include <bits/stdc++.h> using namespace std;
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v): val(v), left(nullptr), right(nullptr) {
    }
};
class Solution {
    public: int widthOfBinaryTree(TreeNode* root) {
        if (!root) return 0;
        int best = 0;
        vector<pair<TreeNode*,long long>> q = { {
            root, 0
        }
        };
        while (!q.empty()) {
            long long first = q[0].second;
            best = max(best, (int)(q.back().second - first + 1));
            vector<pair<TreeNode*,long long>> nq;
            for (auto& pr : q) {
                long long p = pr.second - first;
                if (pr.first->left) nq.push_back({pr.first->left, p * 2});
                if (pr.first->right) nq.push_back({pr.first->right, p * 2 + 1});
            }
            q = nq;
        }
        return best;
    }
};

/**
 * Tree node shape: { val, left, right }
 * @param {TreeNode} root
 * @return {number}
 */ var widthOfBinaryTree = function(root) {
    if (!root) return 0;
    let best = 0, q = [[root, 0]];
    while (q.length) {
        const first = q[0][1];
        best = Math.max(best, q[q.length - 1][1] - first + 1);
        const nq = [];
        for (const [node, idx] of q) {
            const p = idx - first;
            if (node.left) nq.push([node.left, p * 2]);
            if (node.right) nq.push([node.right, p * 2 + 1]);
        }
        q = nq;
    }
    return best;
};

Maximum Width of Binary Tree

Example 1

Example 2

Constraints