algoadvance

You are given the root of a binary tree. The width of a binary tree is the maximum width among all levels. The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes are also counted into the length calculation.

Return the maximum width of the given binary tree.

Constraints:

• The number of nodes in the tree is in the range [1, 3000].
• -100 <= Node.val <= 100

Clarifying Questions

1. Is there a specific data structure for the input tree or a specific way it is represented?
   • Usually, the binary tree nodes are instances of a class TreeNode with attributes val, left, and right.
2. Should we account for null nodes between the leftmost and rightmost nodes?
   • Yes, null nodes between the leftmost and rightmost nodes should be counted in the width.

Strategy

1. Level Order Traversal with Position Tracking:
   • We’ll perform a BFS (Breadth-First Search) traversal to iterate through each level.
   • Use a queue to store tuples of the form (node, index), where index pertains to the “index” of the node in a hypothetical complete binary tree.
   • The width of a level can be calculated using the indices of the leftmost and rightmost nodes at that level.
2. Calculating Width:
   • For each level, we track the minimum and maximum indices. The width of the level is max_index - min_index + 1.
3. Implement BFS:
   • Initialize a queue with the root node and index 0.
   • For each level, process all nodes in the queue, update indices, and calculate the width.

Code

from collections import deque

# 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

def widthOfBinaryTree(root: TreeNode) -> int:
    if not root:
        return 0

    max_width = 0
    queue = deque([(root, 0)])  # Queue contains tuples of (node, index)

    while queue:
        level_size = len(queue)
        _, first_index = queue[0]
        _, last_index = queue[-1]
        max_width = max(max_width, last_index - first_index + 1)

        for _ in range(level_size):
            node, index = queue.popleft()
            if node.left:
                queue.append((node.left, 2 * index))
            if node.right:
                queue.append((node.right, 2 * index + 1))

    return max_width

Time Complexity

• Time Complexity: O(n) where n is the number of nodes in the binary tree. Each node is processed exactly once.
• Space Complexity: O(n) for the queue used in the BFS traversal, which in the worst case (a completely unbalanced tree) can contain all nodes.

This approach ensures an efficient and clear solution to finding the maximum width of a binary tree.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?