Practice › Trees
Maximum Width of a Binary Tree
Medium · Trees · Asked at Amazon, Google, Microsoft
The width of a level is the number of positions between its leftmost and rightmost nodes including the missing nodes in between, as if the tree were complete. Print the maximum width over all levels.
Input
First line: k. Second line: k values — the tree in level order, -1 means no node.
Output
The maximum width.
Constraints
- 1 ≤ number of nodes ≤ 3000
- The tree depth is at most 50
Number positions like a heap: children of i are 2i and 2i+1. Subtract the first index of each level before doubling so the numbers stay small.
Example 1
Input
7 1 3 2 5 3 -1 9
Output
4
Example 2
Input
10 1 3 2 5 -1 -1 9 6 -1 7
Output
7
Hints
- Number the nodes like a heap: the children of index i are 2i and 2i + 1.
- The width of a level is last index − first index + 1. Subtract the first index of the level before computing children so the numbers do not overflow.
Approach
BFS level by level storing (node, index). For each level, the width is last − first + 1. When pushing children, use 2(i − first) and 2(i − first) + 1: re-basing each level keeps every index smaller than twice the width of its level, so with depth ≤ 50 the numbers always fit in an unsigned 64-bit integer. This counts the missing positions between nodes, as required.
Complexity: O(n) time · O(width) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val;
Node *left = nullptr, *right = nullptr;
Node(long long v) : val(v) {}
};
// Build a tree from level order where -1 means "no node".
Node *readTree() {
int k;
cin >> k;
vector<long long> v(k);
for (auto &x : v) cin >> x;
if (k == 0 || v[0] == -1) return nullptr;
Node *root = new Node(v[0]);
queue<Node *> q;
q.push(root);
int i = 1;
while (!q.empty() && i < k) {
Node *cur = q.front();
q.pop();
if (i < k && v[i] != -1) q.push(cur->left = new Node(v[i]));
i++;
if (i < k && v[i] != -1) q.push(cur->right = new Node(v[i]));
i++;
}
return root;
}
int main() {
Node *root = readTree();
unsigned long long best = 0;
vector<pair<Node *, unsigned long long>> level = {{root, 0}};
while (!level.empty()) {
unsigned long long first = level.front().second;
best = max(best, level.back().second - first + 1);
vector<pair<Node *, unsigned long long>> next;
for (auto &p : level) {
unsigned long long i = p.second - first;
if (p.first->left) next.push_back({p.first->left, 2 * i});
if (p.first->right) next.push_back({p.first->right, 2 * i + 1});
}
level = next;
}
cout << best << "\n";
return 0;
}Python solution
import sys
from collections import deque
sys.setrecursionlimit(100000)
class Node:
def __init__(self, val):
self.val, self.left, self.right = val, None, None
def build_tree(v):
"""Build a tree from level order where -1 means "no node"."""
if not v or v[0] == -1:
return None
root = Node(v[0])
q, i = deque([root]), 1
while q and i < len(v):
cur = q.popleft()
if i < len(v) and v[i] != -1:
cur.left = Node(v[i])
q.append(cur.left)
i += 1
if i < len(v) and v[i] != -1:
cur.right = Node(v[i])
q.append(cur.right)
i += 1
return root
data = list(map(int, sys.stdin.read().split()))
k = data[0]
root = build_tree(data[1 : 1 + k])
rest = data[1 + k :]
best, level = 0, [(root, 0)]
while level:
first = level[0][1]
best = max(best, level[-1][1] - first + 1)
nxt = []
for n, i in level:
i -= first
if n.left:
nxt.append((n.left, 2 * i))
if n.right:
nxt.append((n.right, 2 * i + 1))
level = nxt
print(best)Java solution
import java.util.*;
public class Main {
static class Node {
long val;
Node left, right;
Node(long v) { val = v; }
}
// Build a tree from level order where -1 means "no node".
static Node readTree(Scanner sc) {
int k = sc.nextInt();
long[] v = new long[k];
for (int i = 0; i < k; i++) v[i] = sc.nextLong();
if (k == 0 || v[0] == -1) return null;
Node root = new Node(v[0]);
ArrayDeque<Node> q = new ArrayDeque<>();
q.add(root);
int i = 1;
while (!q.isEmpty() && i < k) {
Node cur = q.poll();
if (i < k && v[i] != -1) q.add(cur.left = new Node(v[i]));
i++;
if (i < k && v[i] != -1) q.add(cur.right = new Node(v[i]));
i++;
}
return root;
}
public static void main(String[] args) {
Node root = readTree(new Scanner(System.in));
long best = 0;
List<Node> nodes = new ArrayList<>(List.of(root));
List<Long> idx = new ArrayList<>(List.of(0L));
while (!nodes.isEmpty()) {
long first = idx.get(0);
best = Math.max(best, idx.get(idx.size() - 1) - first + 1);
List<Node> nn = new ArrayList<>();
List<Long> ni = new ArrayList<>();
for (int k = 0; k < nodes.size(); k++) {
Node n = nodes.get(k);
long i = idx.get(k) - first;
if (n.left != null) { nn.add(n.left); ni.add(2 * i); }
if (n.right != null) { nn.add(n.right); ni.add(2 * i + 1); }
}
nodes = nn;
idx = ni;
}
System.out.println(best);
}
}Solve Maximum Width of a Binary Tree online · All practice problems