662. Maximum Width of Binary Tree

Check out the problem description here.

Maximum Width of Binary Tree - LeetCode

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