Maximum Width of Binary Tree

Problem Statement Given the root of a Binary Tree, return its maximum width . The maximum width of a Binary Tree is the maximum number of nodes between the leftmost and rightmost non null nodes at any level. The width of a level is defined as the distance between the index of its leftmost non null node and the index of its rightmost non null node, plus one (inclusive). If a level has only one node, its width is 1. Example 1: Input: Binary Tree: 1 2 3 5 6 1 9 (represented in a level order fashion, where 1 denotes a null node) Output: 4 Explanation: Level 1: [1] (width = 1) Level 2: [2, 3] (width = 2) Level 3: [5, 6, null, 9] (actual nodes: 5, 6, 9). When indexed starting from 0 (where 2 is at index 0 and 3 at index 1), 5 would be index 0 2+1 = 1, 6 would be index 0 2+2 = 2. If 9 is right child of 3 (index 1), its index would be 1 2+2 = 4. The width would be (index of 9 index of 5) + 1. The illustration shows 5, 6, null, 9 spanning 4 positions. If 5 is at relative index 0, 6 at 1, then the null would be at 2, and 9 at 3. Thus, width = 3 0 + 1 = 4. This is the widest level. Example 2: Input: Binary Tree: 1 2 3 5 Output: 2 Explanation: Level 1: [1] (width = 1) Level 2: [2, 3] (width = 2). This is the widest level. Level 3: [5] (width = 1)