# [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)*