[Algorithm/DS] Leetcode#662. 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.
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:
- The number of nodes in the tree is in the range
[1, 3000]. -100 <= Node.val <= 100
Solution:
Lets take an example of below complete binary tree. You might notice that every level, if the number of nodes = n, next level has 2*n nodes present.
Also if we give an index to every node, at every level we can calculate the node position/index as follows:
Left node is positioned at 2i and Right node is positioned at 2i+1 where i is the index of current node we are exploring.
Lets take an example of root node at i=1. So in the next level left node would be at position: 2 * 1 = 2 and right node would be at position: 2 * 1+ 1= 3.
How about we use this idea to find out the width of the tree at any level ?
So in that case what would be the maximum width of the tree here ?
The maximum nodes are at level(d)=4 and width can be calculated with formula as follows:
width_level = maximum node position — minimum node position + 1
= 15–8+1 = 8
Time Complexity: O(N) ; We go through every single node traverse through entire tree.
Space Complexity: O(N)
