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