Maximum Width of Binary Tree
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.
Approach 1:
class Solution {
public int widthOfBinaryTree(TreeNode root) {
if (root == null)
return 0;
// node, col-index
LinkedList> q = new LinkedList<>();
Integer max_width = 0;
q.addLast(new Pair<>(root, 0));
while (q.size() > 0) {
Pair head = q.getFirst();
Integer currLevelSize = q.size();
Pair element = null;
for (int i = 0; i < currLevelSize; i++) {
element = q.removeFirst();
TreeNode node = element.getKey();
if (node.left != null) {
q.addLast(new Pair<>(node.left, 2 * element.getValue()));
}
if (node.right != null) {
q.addLast(new Pair<>(node.right, 2 * element.getValue() + 1));
}
}
max_width = Math.max(max_width, element.getValue() - head.getValue() + 1);
}
return max_width;
}
}
Time Complexity: O(n) and Space Complexity: O(n)
The problem Maximum Width of a Binary Tree involves finding the maximum width of a binary tree. The width of a tree is defined as the number of nodes between the leftmost and rightmost non-null nodes at each level of the tree. The goal is to determine the maximum width across all levels of the tree.
Problem Statement
Given the root of a binary tree, you need to find its maximum width. The width of a level is defined as the number of nodes between the leftmost and rightmost non-null nodes at that level. The maximum width is the largest width of any level in the tree.
Approach to Solve the Problem
To solve this problem, a level-order traversal (BFS) is the most effective method. In BFS, we explore nodes level by level, and we can track the indices of nodes at each level to compute the width. The index of a node in a level is computed based on its position in the queue during the BFS traversal.
Steps to Solve:
- Perform a level-order traversal using a queue.
- For each level, calculate the index of the leftmost and rightmost nodes.
- The difference between the leftmost and rightmost indices at a given level gives the width of that level.
- Keep track of the maximum width across all levels.
Implementation
Here is the Python implementation:
from collections import deque
class Solution:
def widthOfBinaryTree(self, root):
if not root:
return 0
queue = deque([(root, 0)]) # Store node and its index
max_width = 0
while queue:
level_length = len(queue)
_, first_index = queue[0]
for _ in range(level_length):
node, index = queue.popleft()
if node.left:
queue.append((node.left, 2 * index))
if node.right:
queue.append((node.right, 2 * index + 1))
# Update the maximum width
max_width = max(max_width, index - first_index + 1)
return max_width
Here is the Java implementation:
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
public int widthOfBinaryTree(TreeNode root) {
if (root == null) {
return 0;
}
Queue> queue = new LinkedList<>();
queue.offer(new Pair<>(root, 0)); // Store node and its index
int maxWidth = 0;
while (!queue.isEmpty()) {
int levelLength = queue.size();
int firstIndex = queue.peek().getValue();
for (int i = 0; i < levelLength; i++) {
Pair pair = queue.poll();
TreeNode node = pair.getKey();
int index = pair.getValue();
if (node.left != null) {
queue.offer(new Pair<>(node.left, 2 * index));
}
if (node.right != null) {
queue.offer(new Pair<>(node.right, 2 * index + 1));
}
}
maxWidth = Math.max(maxWidth, queue.peek().getValue() - firstIndex + 1);
}
return maxWidth;
}
}
Example
Consider the following binary tree:
Tree Structure:
1
/ \
3 2
/ \ \
5 3 9
For this tree, the maximum width is 4. The maximum width occurs at the second level, where the nodes 5, 3, and 9 are positioned.
Another example is the following tree:
Tree Structure:
1
/ \
2 3
/ \ / \
4 5 6 7
In this case, the maximum width is 4, which occurs at the third level where the nodes 4, 5, 6, and 7 are located.
Complexity Analysis
Time Complexity: O(n), where n is the number of nodes in the binary tree. Each node is processed once during the level-order traversal.
Space Complexity: O(n), where n is the number of nodes. The space complexity arises from the queue used in the level-order traversal, which stores all nodes in the current level.
Applications
- Useful in determining the structure of binary trees and heaps.
- Can be applied in problems involving tree balancing and maintaining hierarchical structures.
- Helps with visualization and representation of trees where the width is an important factor.
Conclusion
The Maximum Width of Binary Tree problem is a classic example of utilizing a level-order traversal (BFS) to determine the width of a binary tree at different levels. The solution efficiently computes the maximum width by leveraging the queue data structure and keeping track of the indices of the nodes at each level. Understanding this approach is crucial for solving problems that require an analysis of the tree's structure and its properties.
This problem also demonstrates the application of breadth-first search and index manipulation, which is a valuable technique for solving various tree-related problems.
