Maximum Width Of Binary Tree - Leetcode Solution

Problem Statement:

Given a binary tree, write a function to get the maximum width of the given tree. The maximum width of a tree is defined as the maximum number of nodes in any level. If the tree is empty, return 0.

Example:

Input:

  1
/   \

3 2 / \
5 3 9

Output: 4

Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).

Solution:

To find the maximum width of the binary tree, we need to traverse the tree level by level and count the number of nodes in each level. We can use a queue for the breadth-first search and a map to store the position of each node in the level.

Algorithm:

1. Initialize a queue to store the nodes of the tree and a map to store the position of each node.

2. Start the breadth-first traversal of the binary tree by adding the root to the queue.

3. While the queue is not empty, process each level of the tree.

4. For each node in the queue, add its left and right child to the queue and update their positions in the map.

5. After processing the current level, update the maximum width with the difference between the leftmost and rightmost positions in the level.

6. Repeat steps 3-5 until the queue is empty.

7. Return the maximum width of the tree.

Pseudo Code:

function max_width_binary_tree(root: TreeNode) -> int: if not root: return 0

queue = [(root, 0)]
level_positions = {}
max_width = 0

while queue:
    level_len = len(queue)
    
    for i in range(level_len):
        node, pos = queue.pop(0)
        level_positions[pos] = node
        
        if node.left:
            queue.append((node.left, 2*pos))
            
        if node.right:
            queue.append((node.right, 2*pos+1))
            
    level_width = level_positions[max(level_positions)]-level_positions[min(level_positions)]+1
    max_width = max(max_width, level_width)
    level_positions.clear()
    
return max_width

Time Complexity:

The time complexity of this algorithm is O(n) as we need to traverse all the nodes of the binary tree.

Space Complexity:

The space complexity of this algorithm is O(n) as we need to store the nodes in the queue and the positions in the map.

1