Sponsored
Sponsored
To solve the problem, we can perform a level order traversal (breadth-first search) of the tree using a queue. Each node will be annotated with a position value, starting with the root being assigned the position 0. As we traverse each level, we calculate the width as the difference between the position of the last node and the first node of that level plus one. This approach ensures that we take into account null positions that would exist in a perfect binary tree.
Time Complexity: O(n), where n is the number of nodes in the tree, as each node is processed exactly once.
Space Complexity: O(w), where w is the maximum width of the tree, held in the queue at any level.
1import java.util.*;
2
3class TreeNode {
4 int val;
5 TreeNode left;
6 TreeNode right;
7 TreeNode() {}
8 TreeNode(int val) { this.val = val; }
9 TreeNode(int val, TreeNode left, TreeNode right) {
10 this.val = val;
11 this.left = left;
12 this.right = right;
13 }
14}
15
16public class Solution {
17 public int widthOfBinaryTree(TreeNode root) {
18 if (root == null) return 0;
19 Deque<Pair<TreeNode, Integer>> queue = new ArrayDeque<>();
20 queue.add(new Pair<>(root, 0));
21 int maxWidth = 0;
22 while (!queue.isEmpty()) {
23 int size = queue.size();
24 int firstPos = queue.getFirst().getValue();
25 int lastPos = firstPos; // initialize to avoid lastPos not being set
26 for (int i = 0; i < size; i++) {
27 Pair<TreeNode, Integer> pair = queue.poll();
28 TreeNode node = pair.getKey();
29 int pos = pair.getValue();
30 if (node.left != null) {
31 queue.add(new Pair<>(node.left, 2 * pos));
32 }
33 if (node.right != null) {
34 queue.add(new Pair<>(node.right, 2 * pos + 1));
35 }
36 lastPos = pos;
37 }
38 maxWidth = Math.max(maxWidth, lastPos - firstPos + 1);
39 }
40 return maxWidth;
41 }
42}
43
44class Pair<K, V> {
45 private final K key;
46 private final V value;
47 public Pair(K key, V value) {
48 this.key = key;
49 this.value = value;
50 }
51 public K getKey() { return key; }
52 public V getValue() { return value; }
53}
54The Java solution uses a custom Pair class to manage node and position pairs in a queue. We calculate level width using the 'position' attribute assigned to each node from the leftmost to rightmost.
An alternative approach involves using depth-first search (DFS) to traverse the tree while maintaining a map of the first position of each level. By keeping track of each node’s depth and position, we can determine the width of any tree level by computing the difference between the first and the current node's position at that depth.
Time Complexity: O(n), visiting each node recursively.
Space Complexity: O(d), where d is the max depth of the tree, accounting for the recursion stack.
1#include <unordered_map>
2#include <algorithm>
3
4struct TreeNode {
5 int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
unsigned long long maxWidth = 0;
std::unordered_map<int, unsigned long long> firstPosMap;
dfs(root, 0, 0, firstPosMap, maxWidth);
return maxWidth;
}
private:
void dfs(TreeNode* node, int depth, unsigned long long position,
std::unordered_map<int, unsigned long long>& firstPosMap, unsigned long long& maxWidth) {
if (!node) return;
if (!firstPosMap.count(depth)) {
firstPosMap[depth] = position;
}
maxWidth = std::max(maxWidth, position - firstPosMap[depth] + 1);
dfs(node->left, depth + 1, 2 * position, firstPosMap, maxWidth);
dfs(node->right, depth + 1, 2 * position + 1, firstPosMap, maxWidth);
}
};
The C++ solution employs a DFS approach to explore the binary tree. We store the initial position for each level and calculate the width using these stored positions.