662. Maximum Width of Binary Tree

Dhanaraj S
2 min readApr 16, 2022

--

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

--

--

Dhanaraj S
Dhanaraj S

Written by Dhanaraj S

Tech-Enthusiast, Coder,Explorer,Geeky,Software Engineer |A piece of code delivers everything that you need. The world is all about codes.