Maximum Width of a Binary Tree (Leetcode 662)

Level Order Traversal

Problem Link: https://leetcode.com/problems/maximum-width-of-binary-tree/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        
        q=[]
        # (node, idx)
        q.insert(0,(root,0))
        max_width=0
        
        while(len(q)>0):
            
            # minn_idx will always be the first
            # element in the level
            minn_idx=q[0][1]
            n=len(q)
            for i in range(n):
                
                popped=q.pop()
                curr,curr_idx = popped[0], popped[1]-minn_idx
                if(i==0):
                    left_most_idx=curr_idx
                if(i==n-1):
                    right_most_idx=curr_idx
                
                if(curr.left is not None):
                    q.insert(0,(curr.left,2*(curr_idx)+1))
                if(curr.right is not None):
                    q.insert(0,(curr.right,2*(curr_idx)+2))
            max_width=max(max_width,right_most_idx-left_most_idx+1)
        
        return max_width