LeetCode 662 | Maximum Width of Binary Tree | Python Solution

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

Video Solution : https://www.youtube.com/watch?v=9NYXVzPCH04&t=2s

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def widthOfBinaryTree(self, root : TreeNode) -> int:
        """
        :type root: TreeNode
        :rtype: int
        """
        width_map = defaultdict(list)
        def helper(root , depth , column):
            if root is None :
                return 
            
            # Add column position to map 
            # width_map[1] = [0,1] <- 0 for 3 and 1 for 2.
            width_map[depth].append(column)
 
            
            left_col = column*2 # Calculate Left Column Position
            right_col = column*2 + 1 # Calculate Right Column Position
      
            left = helper(root.left , depth + 1 , left_col)   
            right = helper(root.right , depth + 1 , right_col)   

        helper(root, 0 , 0 )
        result = 0

        for key in width_map:
            min_val = min(width_map[key]) # Find Minimum for Each Level
            max_val = max(width_map[key]) # Maximum for Each Level
            if result < (max_val - min_val): # Compare Diff with result 
                result = int(max_val - min_val)

        # # # since we are counting from 0 ....to n-1 ex. 0 ,1,2,3 
        # # # total no of nodes are four .. thefoere we return +1 in final result 
        return result + 1