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).
Constraints:
[1, 3000].-100 <= Node.val <= 100To 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.
This Python solution uses a queue to perform a level order traversal. Each node's position is calculated by multiplying its parent position by 2 and adding 1 for right children. The width of each level is calculated using the positions assigned to each node.
Java
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.
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.
This Python solution implements DFS to visit each node, mapping each level's first node position. We calculate width by comparing the position of the current node to this first node's position at each level.
C++
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.
| Approach | Complexity |
|---|---|
| Level Order Traversal with Position Tracking | 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. |
| DFS with Position Tracking | 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. |
L28. Maximum Width of Binary Tree | C++ | Java • take U forward • 317,192 views views
Watch 9 more video solutions →Practice Maximum Width of Binary Tree with our built-in code editor and test cases.
Practice on FleetCode