Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.
The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.
Example 1:
Input: 1
/ \
3 2
/ \ \
5 3 9 Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).
Example 2:
Input: 1
/
3
/ \
5 3 Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).
Example 3:
Input: 1
/ \
3 2
/
5 Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).
Example 4:
Input: 1
/ \
3 2
/ \
5 9
/ \
6 7
Output: 8
Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).
Note: Answer will in the range of 32-bit signed integer.
Solution Approach:
Consider the following example of a binary tree. We will use a pair, (node, value) in which node would be the current node in consideration and value
1
/ \
2 3
/ \ /\
4 5 6 7would be the position of the node from right to left in that level. So, for the above tree, the pairs would be like:
(1,1)
(2,2), (3,1)
(4,4), (5,3), (6,2), (7,1)
Now, to fill the value in the pairs, if the root node is (node, val), for its left the pair would be (node->left, 2*val) and the right would be (node->right, 2*val-1). The width of the tree at any level will be leftmost_position — rightmost_position +1. So, for the above example tree, at level 2, the width is 4 –1+1 = 4. Do the same for every level of the tree, the max width is the answer.
The time complexity of this approach is O(N) where N is the number of nodes in the tree.