# 662. Maximum Width of Binary Tree

--

Check out the problem description here.

*Approach 1:*

Traverse level by level. Store all the nodes in the level , including the null values. For each level find left most and right most non null nodes and find the maximum width

**Time limit exceeded.**

Given the maximum number of nodes can be 3000. Assuming If the tree is skew, then the while loop runs 3000 times, and the for loops may run at max 2³⁰⁰⁰ , which can give time limit exceeded.

class Solution:

def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:

q,res=[],0

if root:

q=[root]

res = self.func(q) return res

def func(self,q):

max_=0

while(q):

size = len(q)

left=-1

right=0

for i in range(size):

front=q.pop(0)

if front==None:

q.append(None)

q.append(None)

else:

if left==-1:

left=i

right=i

q.append(front.left)

q.append(front.right)

all_false=1

for i in q:

if i!=None:

all_false=0

break

if all_false:

q=[]

max_=max(max_,right-left)

return max_+1

*Time: O(2^n) for skew tree*

*Space: O(2^n) for skew tree*

*Approach 2:*

The same approach 1 in a better way is given below.

We know that left and right child of a node is at position 2^n+1 and 2^n+2 respectively(0 based indexing). This idea can be used here, so that max width can be found. We will use the same level order traversal, but will push an item in to q which contain the node and position of it in the tree, so that max width in the tree can be found.

`class Solution:`

def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:

q=[(root,0)]

max_width=1

while(q):

size = len(q)

max_width= max(max_width,q[-1][1] - q[0][1] + 1)

for i in range(size):

node,pos=q.pop(0)

if node.left:

q.append((node.left,2*pos+1))

if node.right:

q.append((node.right,2*pos+2))

return max_width

*Time: O(n) for skew tree*

*Space: O(n) for skew tree*