Maximum Width of Binary Tree LeetCode Solution

Quoestion:Click Here

Approach Using BFS:

we use BFS or level order traversal.we keep tarck of level,index of each node in queue for calculating max width.

Algorithm:

1.if root=null;return 0

2.create a queue to store the index,level,TreeNode

3.we fill indexes according to the following

    indexof_leftchild = (2*(index_of_root))

    indexof_rightchild = (2*(index_of_root)+1)

4.we pop the first item in queue and check for level if cur_level > prev_level we update them

5.maximum width will be max(prev_width,(cur_idx-idx_old)+1)

6.return maxwidth

TimeComplexity:O(N)

SpaceComplexity:O(N)

Python Code:

# 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:

    def widthOfBinaryTree(self, root):

        prev_level, idx_old, result = 1, 1, 0

        queue = [[prev_level,idx_old,root]]

        while queue:    

            [cur_idx, cur_level, node] = queue.pop(0)

            if cur_level > prev_level:

                prev_level, idx_old = cur_level, cur_idx

            result = max(result, cur_idx - idx_old + 1)

            if node.left:  queue.append([cur_idx*2,  cur_level+1, node.left])

            if node.right: queue.append([cur_idx*2+1,cur_level+1, node.right])

                

        return result

Try Problem In LeetCode