Maximum Width of Binary Tree

Medium
1926.

Maximum Width of Binary Tree

Maximum Width of Binary Tree is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google, Microsoft and Meta interviews.

Given the root of a binary tree, return its maximum width — the largest width among all its levels.

The width of a level is the number of positions between its leftmost and rightmost non-null nodes, both included, counting the empty slots in between as they would be in a complete binary tree reaching that level.

The answer is guaranteed to fit in a 32-bit signed integer.

Example 1

Input
root = [1,3,2,5,3,null,9]
Output
4
Explanation
The widest level is the third: from 5 to 9 it spans four positions (5, 3, an empty slot, 9).

Example 2

Input
root = [1,3,2,5,null,null,9,6,null,7]
Output
7
Explanation
On the fourth level 6 sits at the far left and 7 at the far right of a span of seven positions; the five empty slots between them count.

Example 3

Input
root = [1,3,2,5]
Output
2
Explanation
The second level, 3 and 2, has width 2; the third holds only 5.

Constraints

  • The number of nodes in the tree is in the range [1, 3000]
  • -100 <= Node.val <= 100
  • The answer fits in a 32-bit signed integer
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var widthOfBinaryTree = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Width of Binary Tree — Problem & Solution

Maximum Width of Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Width of Binary Tree is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google, Microsoft and Meta interviews.

Problem statement

Given the root of a binary tree, return its maximum width — the largest width among all its levels.

The width of a level is the number of positions between its leftmost and rightmost non-null nodes, both included, counting the empty slots in between as they would be in a complete binary tree reaching that level.

The answer is guaranteed to fit in a 32-bit signed integer.

Example 1

Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The widest level is the third: from 5 to 9 it spans four positions (5, 3, an empty slot, 9).

Example 2

Input: root = [1,3,2,5,null,null,9,6,null,7]
Output: 7
Explanation: On the fourth level 6 sits at the far left and 7 at the far right of a span of seven positions; the five empty slots between them count.

Example 3

Input: root = [1,3,2,5]
Output: 2
Explanation: The second level, 3 and 2, has width 2; the third holds only 5.

Constraints

  • The number of nodes in the tree is in the range [1, 3000]
  • -100 <= Node.val <= 100
  • The answer fits in a 32-bit signed integer

Hints for Maximum Width of Binary Tree

  1. Hint 1

    Number the positions as in a heap: the root is 0, and a node at position i has children at 2i and 2i + 1.

  2. Hint 2

    A level's width is then (last position − first position + 1) — a breadth-first walk gives you each level's first and last node.

  3. Hint 3

    Positions double on every level and overflow after ~60 levels even in 64 bits. Subtract each level's first position before computing the children's positions.

How to solve Maximum Width of Binary Tree

Give every node the index it would have in a complete binary tree. Within one level, the width is the difference between the rightmost and leftmost indices plus one, null slots included automatically. Re-basing each level's indices at its leftmost node keeps the numbers small.

Approach

  1. Start a BFS with (root, 0).
  2. For each level, let first be the index of its first node and last that of its last; update best = max(best, last - first + 1).
  3. For every node of the level with index i, let j = i - first and enqueue its left child with 2j and its right child with 2j + 1.
  4. Return best after the last level.

Why it works

In a complete-tree numbering, positions on a level are consecutive integers, so the count of slots between two nodes is the difference of their indices plus one. Subtracting the same first from every index on a level shifts the next level's indices by a constant, which leaves every difference — and so every width — unchanged.

Complexity

  • Time — O(n)
  • Space — O(w) for one level, w being the widest level

Pitfalls

  • Without re-basing, indices on a deep, skinny tree grow like 2^depth and overflow any fixed-width integer.
  • Even after re-basing, 2j + 1 can reach about 2^32 on a level whose width is near the limit — compute indices in 64 bits.
  • Empty slots between the end nodes count; nulls outside them do not.

Reference solution

Python

from typing import Optional

def widthOfBinaryTree(root: Optional[TreeNode]) -> int:
    best = 0
    level = [(root, 0)]
    while level:
        first = level[0][1]
        best = max(best, level[-1][1] - first + 1)
        nxt = []
        for node, i in level:
            j = i - first
            if node.left is not None:
                nxt.append((node.left, 2 * j))
            if node.right is not None:
                nxt.append((node.right, 2 * j + 1))
        level = nxt
    return best

Java

public static int widthOfBinaryTree(TreeNode root) {
    long best = 0;
    List<TreeNode> nodes = new ArrayList<>();
    List<Long> idx = new ArrayList<>();
    nodes.add(root);
    idx.add(0L);
    while (!nodes.isEmpty()) {
        long first = idx.get(0);
        best = Math.max(best, idx.get(idx.size() - 1) - first + 1);
        List<TreeNode> nn = new ArrayList<>();
        List<Long> ni = new ArrayList<>();
        for (int k = 0; k < nodes.size(); k++) {
            long j = idx.get(k) - first;
            TreeNode cur = nodes.get(k);
            if (cur.left != null) { nn.add(cur.left); ni.add(2 * j); }
            if (cur.right != null) { nn.add(cur.right); ni.add(2 * j + 1); }
        }
        nodes = nn;
        idx = ni;
    }
    return (int) best;
}

C++

int widthOfBinaryTree(TreeNode* root) {
    long long best = 0;
    vector<pair<TreeNode*, long long>> level = {{root, 0}};
    while (!level.empty()) {
        long long first = level.front().second;
        best = max(best, level.back().second - first + 1);
        vector<pair<TreeNode*, long long>> next;
        for (auto& p : level) {
            long long j = p.second - first;
            if (p.first->left) next.push_back({p.first->left, 2 * j});
            if (p.first->right) next.push_back({p.first->right, 2 * j + 1});
        }
        level.swap(next);
    }
    return (int) best;
}

JavaScript

var widthOfBinaryTree = function(root) {
    var best = 0;
    var nodes = [root], idx = [0];
    while (nodes.length > 0) {
        var first = idx[0];
        best = Math.max(best, idx[idx.length - 1] - first + 1);
        var nn = [], ni = [];
        for (var k = 0; k < nodes.length; k++) {
            var j = idx[k] - first;
            if (nodes[k].left !== null) { nn.push(nodes[k].left); ni.push(2 * j); }
            if (nodes[k].right !== null) { nn.push(nodes[k].right); ni.push(2 * j + 1); }
        }
        nodes = nn;
        idx = ni;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)