662. Maximum Width of Binary Tree LeetCode Solution
In this guide, you will get 662. Maximum Width of Binary Tree LeetCode Solution with the best time and space complexity. The solution to Maximum Width of Binary Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Given the root of a binary tree, return the maximum width of the given tree.
The maximum width of a tree is the maximum width among all levels.
The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.
It is guaranteed that the answer will in the range of a 32-bit signed integer.
Example 1:
Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).
Example 2:
Input: root = [1,3,2,5,null,null,9,6,null,7]
Output: 7
Explanation: The maximum width exists in the fourth level with length 7 (6,null,null,null,null,null,7).
Example 3:
Input: root = [1,3,2,5]
Output: 2
Explanation: The maximum width exists in the second level with length 2 (3,2).
The number of nodes in the tree is in the range [1, 3000].
-100 <= Node.val <= 100
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(h)
662. Maximum Width of Binary Tree LeetCode Solution in C++
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if (root == nullptr)
return 0;
int ans = 0;
queue<pair<TreeNode*, int>> q{{{root, 1}}}; // {node, index}
while (!q.empty()) {
const int offset = q.front().second * 2;
ans = max(ans, q.back().second - q.front().second + 1);
for (int sz = q.size(); sz > 0; --sz) {
const auto [node, index] = q.front();
q.pop();
if (node->left)
q.emplace(node->left, index * 2 - offset);
if (node->right)
q.emplace(node->right, index * 2 + 1 - offset);
}
}
return ans;
}
}; /* code provided by PROGIEZ */
662. Maximum Width of Binary Tree LeetCode Solution in Java
class Solution {
public int widthOfBinaryTree(TreeNode root) {
if (root == null)
return 0;
int ans = 0;
// {node, index}
Deque<Pair<TreeNode, Integer>> q = new ArrayDeque<>(List.of(new Pair<>(root, 1)));
while (!q.isEmpty()) {
final int offset = q.peekFirst().getValue() * 2;
ans = Math.max(ans, q.peekLast().getValue() - q.peekFirst().getValue() + 1);
for (int sz = q.size(); sz > 0; --sz) {
final TreeNode node = q.peekFirst().getKey();
final int index = q.pollFirst().getValue();
if (node.left != null)
q.offer(new Pair<>(node.left, index * 2 - offset));
if (node.right != null)
q.offer(new Pair<>(node.right, index * 2 + 1 - offset));
}
}
return ans;
}
} // code provided by PROGIEZ
662. Maximum Width of Binary Tree LeetCode Solution in Python
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if (root == nullptr)
return 0;
long ans = 0;
dfs(root, 0, 1, {}, ans);
return ans;
}
private:
void dfs(TreeNode* root, int level, long index, vector<long>&& startOfLevel,
long& ans) {
if (root == nullptr)
return;
if (startOfLevel.size() == level)
startOfLevel.push_back(index);
ans = max(ans, index - startOfLevel[level] + 1);
dfs(root->left, level + 1, index * 2, std::move(startOfLevel), ans);
dfs(root->right, level + 1, index * 2 + 1, std::move(startOfLevel), ans);
}
}; # code by PROGIEZ
