from collections import deque
class Solution:
def widthOfBinaryTree(self, root):
if not root:
return 0
max_width = 0
queue = deque([(root, 0)]) # (node, index)
while queue:
level_length = len(queue)
_, first_index = queue[0]
for i in range(level_length):
node, idx = queue.popleft()
if node.left:
queue.append((node.left, 2 * idx))
if node.right:
queue.append((node.right, 2 * idx + 1))
# last node's index in this level
last_index = idx
max_width = max(max_width, last_index - first_index + 1)
return max_width
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
#include <queue>
using namespace std;
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if (!root) return 0;
unsigned long long maxWidth = 0;
queue<pair<TreeNode*, unsigned long long>> q;
q.push({root, 0});
while (!q.empty()) {
int levelSize = q.size();
unsigned long long firstIndex = q.front().second;
unsigned long long lastIndex = 0;
for (int i = 0; i < levelSize; ++i) {
auto node_pair = q.front(); q.pop();
TreeNode* node = node_pair.first;
unsigned long long idx = node_pair.second;
lastIndex = idx;
if (node->left)
q.push({node->left, 2 * idx});
if (node->right)
q.push({node->right, 2 * idx + 1});
}
maxWidth = max(maxWidth, lastIndex - firstIndex + 1);
}
return (int)maxWidth;
}
};
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
import java.util.*;
public class Solution {
public int widthOfBinaryTree(TreeNode root) {
if (root == null) return 0;
int maxWidth = 0;
Queue<Pair> queue = new LinkedList<>();
queue.offer(new Pair(root, 0));
while (!queue.isEmpty()) {
int size = queue.size();
int firstIndex = queue.peek().idx;
int lastIndex = 0;
for (int i = 0; i < size; ++i) {
Pair p = queue.poll();
TreeNode node = p.node;
int idx = p.idx;
lastIndex = idx;
if (node.left != null)
queue.offer(new Pair(node.left, 2 * idx));
if (node.right != null)
queue.offer(new Pair(node.right, 2 * idx + 1));
}
maxWidth = Math.max(maxWidth, lastIndex - firstIndex + 1);
}
return maxWidth;
}
}
class Pair {
TreeNode node;
int idx;
Pair(TreeNode node, int idx) {
this.node = node;
this.idx = idx;
}
}
/**
* Definition for a binary tree node.
* 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) {
if (!root) return 0;
let maxWidth = 0;
let queue = [[root, 0]];
while (queue.length > 0) {
let levelLength = queue.length;
let firstIndex = queue[0][1];
let lastIndex = 0;
for (let i = 0; i < levelLength; i++) {
let [node, idx] = queue.shift();
lastIndex = idx;
if (node.left) queue.push([node.left, 2 * idx]);
if (node.right) queue.push([node.right, 2 * idx + 1]);
}
maxWidth = Math.max(maxWidth, lastIndex - firstIndex + 1);
}
return maxWidth;
};
Given the root node of a binary tree, you are to find the maximum width of the tree. The width of a binary tree at a particular level is defined as the length between the leftmost and rightmost non-null nodes at that level (including the null nodes in between). The tree may not be complete or balanced, and nodes may be missing at any position.
The input is a binary tree represented by its root node. The output is an integer representing the maximum width among all levels of the tree.
last_index - first_index + 1, where first_index and last_index are the indices of the leftmost and rightmost non-null nodes at that level, respectively.i, its left child is at 2*i and right child at 2*i + 1.At first glance, you might consider traversing each level and counting the number of nodes. However, because the tree can have missing nodes (not a complete tree), simply counting nodes per level does not give the correct width. Instead, we need a way to account for the "gaps" created by missing nodes.
The key insight is to assign a positional index to each node as if the tree were a complete binary tree. This allows us to calculate the width by comparing the indices of the leftmost and rightmost nodes at each level, even if there are missing nodes between them.
A brute-force approach would involve reconstructing the tree with explicit nulls or traversing all possible positions, but this is inefficient. Instead, we can use a queue for level-order traversal (BFS), keeping track of each node's index. This way, we can efficiently compute the width at each level as we go.
i:
2 * i2 * i + 1last_index - first_index + 1. Update the maximum width found so far.
(node, index).Consider the following binary tree:
1
/ \
3 2
/ \
5 9
/ \
6 7
At each step, we record the indices of the first and last nodes in the queue for that level, and compute the width accordingly.
The maximum width of a binary tree can be efficiently computed by assigning indices to nodes as if the tree were complete, and performing a level-order traversal while tracking the leftmost and rightmost indices at each level. This approach elegantly handles missing nodes and avoids the inefficiency of brute-force methods. The key insight is using positional indices to represent potential nulls, allowing for a simple and efficient O(N) solution.