☕ DSA Java Articles

Topics › Binary Trees › Hard Problems

Maximum Width of BT

Medium TUF ID 119 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the root of a binary tree. The width of a level is the number of positions between its leftmost and rightmost nodes, inclusive, where the gaps count too: imagine the level filled in as if the tree were complete, and count every slot from the first real node to the last one. Return the maximum width over all levels.

Constraints (LeetCode): up to 3000 nodes, and the answer is guaranteed to fit in a 32-bit signed integer. We return 0 for an empty tree.

Example 1

         1
       /   \
      3     2
     / \     \
    5   3     9

answer = 4

The last level is 5, 3, _, 9: the empty slot under 2’s left side counts, giving width 4.

Example 2

           1
         /   \
        3     2
       /       \
      5         9
     /         /
    6         7

answer = 7

On the last level, 6 sits in slot 0 and 7 in slot 6 of a complete level, so the width is 6 - 0 + 1 = 7, even though only two nodes exist there.

Approach 1: Brute force, keep the gaps as placeholders

Intuition. Take the definition literally. Do a level-order traversal, but keep a null placeholder for every missing position. A placeholder has two placeholder children, so the positions of real nodes stay correct. After building the next level, trim the placeholders from both ends, because the width only counts from the first real node to the last. The length of the trimmed level is then exactly its width.

The trouble is that placeholders multiply. A tree with one long arm going left and another going right has only two real nodes per level, but the gap between them doubles every level. After d levels we store 2^d slots. With 3000 nodes this is hopeless.

Algorithm.

  1. Start with the level [root].
  2. Record level.size() as a candidate width.
  3. Build the next level: for every slot, append its left and right child, or two nulls for a placeholder.
  4. Trim nulls at both ends. Stop when nothing is left.
static int bruteForce(TreeNode root) {
    if (root == null) return 0;
    List<TreeNode> level = new ArrayList<>();
    level.add(root);
    int best = 0;
    while (!level.isEmpty()) {
        best = Math.max(best, level.size());                  // the level is trimmed, so its size is its width
        List<TreeNode> next = new ArrayList<>();
        for (TreeNode node : level) {
            next.add(node == null ? null : node.left);        // a gap has two gap children
            next.add(node == null ? null : node.right);
        }
        int lo = 0, hi = next.size() - 1;                     // trim placeholders at both ends
        while (lo <= hi && next.get(lo) == null) lo++;
        while (hi >= lo && next.get(hi) == null) hi--;
        level = new ArrayList<>(next.subList(lo, hi + 1));
    }
    return best;
}

Complexity. Time and space are the sum of all level widths, which can reach O(2^h). It is useful only to confirm the definition on small trees.

Approach 2: Number the nodes like a heap, with DFS

Intuition. We do not need the placeholders, only the positions they create. Number the slots of each level the way an array-based heap does: the root is index 0, the left child of index i is 2i, and the right child is 2i + 1. These numbers are positions in a complete level, so the width of a level is last index - first index + 1.

The catch is size. Indices double at every level, so after 63 levels they no longer fit in a long. Java does not fail on overflow; it silently wraps around, which makes the bug hard to notice. The fix is to re-base: on every level, subtract the leftmost index of that level before computing children. Subtracting the same constant f from every index on a level changes all children by the same 2f, so differences on the next level, and therefore widths, are unchanged. Re-based indices stay below twice the level’s width.

With a DFS, the leftmost node of each depth is the first node the preorder walk reaches at that depth, so we record that index in a list firstAtDepth and compute every node’s width and children relative to it.

Algorithm.

  1. DFS with (node, depth, index), starting at (root, 0, 0).
  2. If this is the first node at depth, store index as firstAtDepth[depth].
  3. Candidate width: index - first + 1.
  4. Children get 2 * (index - first) and 2 * (index - first) + 1. Return the largest width found in this subtree.
static int dfs(TreeNode root) {
    return (int) dfsWidth(root, 0, 0L, new ArrayList<>());
}

static long dfsWidth(TreeNode node, int depth, long index, List<Long> firstAtDepth) {
    if (node == null) return 0;
    if (depth == firstAtDepth.size()) firstAtDepth.add(index);   // preorder meets the leftmost node of a depth first
    long first = firstAtDepth.get(depth);
    long width = index - first + 1;
    long childBase = 2 * (index - first);                     // children numbered relative to the leftmost node
    width = Math.max(width, dfsWidth(node.left, depth + 1, childBase, firstAtDepth));
    width = Math.max(width, dfsWidth(node.right, depth + 1, childBase + 1, firstAtDepth));
    return width;
}

Complexity. Time O(n): one visit per node. Space O(h) for the recursion and the firstAtDepth list.

Approach 3: Optimal, BFS with re-based indices

Intuition. Width is a per-level quantity, so level-order traversal is the natural fit, and it makes re-basing trivial. Process one level at a time. The front of the queue is the leftmost node of the level, so its index is first. Subtract first from every index of the level as you pop it, then push children with 2 * idx and 2 * idx + 1. The last node popped has the largest re-based index last, and the width of the level is last + 1.

Algorithm.

  1. Push (root, 0).
  2. For each level: read first from the front of the queue, pop size entries.
  3. For each entry: idx = stored - first; push children with 2 * idx and 2 * idx + 1.
  4. After the level, update the answer with last + 1.
static int optimal(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> nodes = new ArrayDeque<>();
    Queue<Long> indices = new ArrayDeque<>();
    nodes.add(root);
    indices.add(0L);
    long best = 0;
    while (!nodes.isEmpty()) {
        int size = nodes.size();
        long first = indices.peek();                          // index of the leftmost node on this level
        long last = 0;
        for (int i = 0; i < size; i++) {
            TreeNode node = nodes.poll();
            long idx = indices.poll() - first;                // re-base so this level starts at 0
            last = idx;
            if (node.left != null) { nodes.add(node.left); indices.add(2 * idx); }
            if (node.right != null) { nodes.add(node.right); indices.add(2 * idx + 1); }
        }
        best = Math.max(best, last + 1);                      // last is already relative to the leftmost node
    }
    return (int) best;
}

Dry run on Example 2:

level nodes (stored index) first re-based width
0 1 (0) 0 0 1
1 3 (0), 2 (1) 0 0, 1 2
2 5 (0), 9 (3) 0 0, 3 4
3 6 (0), 7 (6) 0 0, 6 7

9 is the right child of index 1, so it gets 3; 7 is the left child of 3, so it gets 6. The answer is 7.

Complexity. Time O(n): each node is pushed and popped once. Space O(w), where w is the largest number of real nodes on a level.

Edge cases and pitfalls