grid47 Exploring patterns and algorithms
Sep 1, 2024
6 min read
Solution to LeetCode 662: Maximum Width of Binary Tree Problem
You are given the root of a binary tree. Determine the maximum width of the tree, which is defined as the maximum width among all levels. The width of a level is the distance between the leftmost and rightmost non-null nodes, including null nodes in between that would be present in a complete binary tree.
Problem
Approach
Steps
Complexity
Input: The input consists of the root of a binary tree represented as an array of integers, where each integer is a node value or null if the node does not exist.
Example: root = [1, 3, 2, 5, 3, null, 9]
Constraints:
• 1 <= number of nodes <= 3000
• -100 <= Node.val <= 100
Output: The output is a single integer representing the maximum width of the binary tree.
Example: 4
Constraints:
• The output is guaranteed to be within the range of a 32-bit signed integer.
Goal: The goal is to compute the maximum width of the binary tree by finding the maximum width across all levels of the tree.
Steps:
• 1. Use a breadth-first search (BFS) approach to traverse the tree level by level.
• 2. At each level, compute the width by calculating the difference between the positions of the leftmost and rightmost non-null nodes.
• 3. Keep track of the maximum width encountered during the traversal.
Goal: The binary tree has at most 3000 nodes, and node values range between -100 and 100.
Steps:
• 1 <= number of nodes <= 3000
• -100 <= Node.val <= 100
Assumptions:
• The binary tree is represented as a complete binary tree with null values for missing nodes.
• Input: root = [1, 3, 2, 5, 3, null, 9]
• Explanation: The maximum width is at level 3 with the nodes [5, 3, null, 9], which gives a width of 4.
• Explanation: The maximum width is at level 4 with the nodes [6, null, null, null, null, null, 7], which gives a width of 7.
Approach: The approach for this problem uses a breadth-first search (BFS) to traverse the tree level by level, calculating the width at each level.
Observations:
• We can use BFS to explore each level of the tree.
• To calculate the width, we need to track the positions of nodes at each level.
• We should be able to find the width by using a queue to track the nodes and their positions in the tree.
Steps:
• 1. Initialize a queue with the root node and its position.
• 2. Process each level of the tree, updating the width based on the positions of the leftmost and rightmost non-null nodes.
• 3. Repeat this process until all levels of the tree have been processed.
Empty Inputs:
• The tree will always have at least one node.
Large Inputs:
• The algorithm needs to handle large trees with up to 3000 nodes efficiently.
Special Values:
• If a tree contains null values at various positions, these should be counted when calculating the width of the tree.
Constraints:
• Ensure that the width is calculated by including null nodes in the level width.
intwidthOfBinaryTree(TreeNode* root) {
if(root ==NULL) return0;
queue<pair<TreeNode*, int>> q;
int width =0;
q.push({root, 0});
while(!q.empty()) {
int f = q.front().second;
int b = q.back().second;
int cnt = q.size();
for(int i =0; i < cnt; i++) {
TreeNode* elem = q.front().first;
int idx = q.front().second - b;
q.pop();
if(elem->left !=NULL) q.push({elem->left, 2* idx +1});
if(elem->right !=NULL) q.push({elem->right, 2* idx +2});
}
width = max(width, b - f +1);
}
return width;
}
1 : Function Definition
intwidthOfBinaryTree(TreeNode* root) {
This is the function definition for `widthOfBinaryTree`, which calculates the maximum width of a binary tree. It takes the root node of the tree as input and returns an integer value representing the width.
2 : Base Case
if(root ==NULL) return0;
If the tree is empty (root is NULL), return 0 as the width.
3 : Queue Initialization
queue<pair<TreeNode*, int>> q;
Initialize a queue `q` to store pairs of nodes and their corresponding indices in the tree. The index helps track the position of nodes at each level.
4 : Width Initialization
int width =0;
Initialize a variable `width` to track the maximum width of the tree, starting with a value of 0.
5 : Initial Node Push
q.push({root, 0});
Push the root node into the queue with an index of 0.
6 : While Loop Start
while(!q.empty()) {
Start a `while` loop that continues as long as the queue is not empty, processing each level of the tree.
7 : Front Node Index
int f = q.front().second;
Get the index of the first node in the queue. This index represents the position of the leftmost node at the current level.
8 : Back Node Index
int b = q.back().second;
Get the index of the last node in the queue. This index represents the position of the rightmost node at the current level.
9 : Queue Size
int cnt = q.size();
Get the number of nodes at the current level by checking the size of the queue.
10 : Level Processing Loop
for(int i =0; i < cnt; i++) {
Start a loop to process each node at the current level.
11 : Pop Front Node
TreeNode* elem = q.front().first;
Pop the first node from the queue and retrieve the node itself (`elem`).
12 : Calculate Node Index
int idx = q.front().second - b;
Calculate the adjusted index for the current node by subtracting the index of the rightmost node (`b`). This helps to prevent overflow and handle large trees efficiently.
If the current node has a right child, push it to the queue with its new index calculated as `2 * idx + 2`.
16 : Update Maximum Width
width = max(width, b - f +1);
Update the `width` variable with the maximum width of the current level, calculated as the difference between the indices of the last and first nodes, plus one.
17 : Return Result
return width;
Return the maximum width of the binary tree.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we process each node once during the BFS traversal.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) because we use a queue to store nodes during the BFS traversal.
