How to Determine Maximum width of a Binary Tree

Introduction

In binary tree problems, the width of a tree at any given level refers to the total number of nodes present between the leftmost and rightmost non-null nodes, counting the null nodes that may exist in between. This concept is especially useful in scenarios such as UI layouts or serialization, where the structure and completeness of the tree matter. In this article, you will learn how to determine the maximum width of a binary tree.

Problem Statement

Given the root of a binary tree, determine the maximum width among all levels. The width of a level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), using the position they would have in a complete binary tree.

Key Concept

To simulate the layout of a complete binary tree, we assign each node a position index:

• For a node at index i, the left child is assigned index 2*i
• The right child is assigned index 2*i + 1

This indexing helps us measure distances between nodes across all levels, even when some children are missing (i.e., null).

Java Implementation

Below is a Java implementation using Breadth-First Search (BFS) with position indexing to compute the maximum width.

public class BinaryTreeWidth {
	
    static class BinTreeNode {
        int val;
        BinTreeNode left, right;
        BinTreeNode(int x) { val = x; }
    }

    static class NodeIndexPair {
        BinTreeNode node;
        int index;
        NodeIndexPair(BinTreeNode node, int index) {
            this.node = node;
            this.index = index;
        }
    }

    public int widthOfBinaryTree(BinTreeNode root) {
        if (root == null) return 0;

        int maxWidth = 0;
        Queue<NodeIndexPair> q = new LinkedList<>();
        q.offer(new NodeIndexPair(root, 0));

        while (!q.isEmpty()) {
            int size = q.size();
            int levelStart = q.peek().index;
            int levelEnd = levelStart;

            for (int i = 0; i < size; i++) {
                NodeIndexPair current = q.poll();
                BinTreeNode node = current.node;
                int index = current.index;

                levelEnd = index;

                if (node.left != null) {
                    q.offer(new NodeIndexPair(node.left, 2 * index));
                }
                if (node.right != null) {
                    q.offer(new NodeIndexPair(node.right, 2 * index + 1));
                }
            }
            maxWidth = Math.max(maxWidth, levelEnd - levelStart + 1);
        }

        return maxWidth;
    }

    public static void main(String[] args) {
        BinaryTreeWidth solver = new BinaryTreeWidth();
        BinTreeNode root = new BinTreeNode(1);
        root.left = new BinTreeNode(3);
        root.right = new BinTreeNode(2);
        root.left.left = new BinTreeNode(5);
        root.left.right = new BinTreeNode(3);
        root.right.right = new BinTreeNode(9);

        int result = solver.widthOfBinaryTree(root);
        System.out.println("Maximum width: " + result); // Output should be 4
    }
}

Explanation

The algorithm uses a queue to perform a level-order traversal, assigning indices to each node to reflect their theoretical position in a complete tree. The maximum width is calculated as the difference between the first and last index at each level.

In the provided example, the maximum width is found at the last level, which contains the nodes [5, null, null, 9] — resulting in a width of 4 (positions 0 to 3 inclusive).

Conclusion

Computing the maximum width of a binary tree by tracking node positions as in a complete binary tree ensures an accurate measurement, even when the tree is sparse. This method is both efficient and reliable for identifying structural imbalances or bottlenecks in tree-based systems.

You can find the example code on Github.