Naive Approach (Brute Force)

A brute force approach to solve this problem would involve performing a level-order traversal of the tree. During the level-order traversal, we'd keep track of the leftmost and rightmost non-null nodes at each level. The width of the level would then be the difference between the indices of these two nodes plus one. We would maintain a global maximum width and update it at each level.

However, this approach requires us to store null nodes in the queue to maintain the structure of the complete binary tree, which can be space-consuming, especially for skewed trees.

Optimal Approach

The optimal approach also involves a level-order traversal, but it leverages the property of a complete binary tree to assign indices to nodes implicitly. The root node gets index 0. If a node has index i, its left child gets index 2*i, and its right child gets index 2*i + 1. This allows us to track the leftmost and rightmost indices at each level without actually storing the null nodes.

1. Initialization: Start with a queue containing the root node and its index (0).
2. Level-order Traversal: While the queue is not empty, process nodes level by level.
3. Level Processing: For each level, find the index of the leftmost and rightmost nodes.
4. Width Calculation: The width of the level is the rightmost index minus the leftmost index plus 1.
5. Update Max Width: Keep track of the maximum width seen so far.
6. Enqueue Children: Add the left and right children of the current node to the queue along with their respective indices.

Edge Cases

• If the root is null, the width is 0.
• For a single-node tree, the width is 1.
• Handle integer overflow. Since the indices can grow as 2*i, using a wider type (e.g., long in Java) prevents potential overflow issues.

Code (Java)

import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(root, 0));
        int maxWidth = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            int left = queue.peek().getValue();
            int right = 0;

            for (int i = 0; i < size; i++) {
                Pair<TreeNode, Integer> current = queue.poll();
                TreeNode node = current.getKey();
                int index = current.getValue();

                if (i == size - 1) {
                    right = index;
                }

                if (node.left != null) {
                    queue.offer(new Pair<>(node.left, 2 * index));
                }
                if (node.right != null) {
                    queue.offer(new Pair<>(node.right, 2 * index + 1));
                }
            }

            maxWidth = Math.max(maxWidth, right - left + 1);
        }

        return maxWidth;
    }

    static class Pair<K, V> {
        private final K key;
        private final V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }
}

Complexity Analysis

• Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited once.
• Space Complexity: O(W), where W is the maximum width of the tree. In the worst case (a complete binary tree), W can be up to N, so the space complexity can be O(N).