We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Width of Binary Tree

Number: 662

Difficulty: Medium

Paid? No

Companies: Google, Amazon, TikTok, Meta, Uber, Bloomberg, Apple, Adobe

Problem Description

Given the root of a binary tree, determine the maximum width of the tree. The width of a level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), including the null nodes that would be present in a complete binary tree. Return the maximum width among all levels.

Key Insights

  • Perform a level order traversal (BFS) of the tree.
  • Assign an index to each node as if the tree were complete (e.g., root is index 1, left child is 2i, right child is 2i+1).
  • For each level, compute the width as (last_index - first_index + 1).
  • Using indices allows capturing gaps between nodes due to nulls in between.
  • Edge cases include handling very skewed trees.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree. Space Complexity: O(N), due to the queue used for BFS which in the worst case holds nodes of the last level.

Solution

We use a Breadth-First Search (BFS) approach with a queue to traverse the tree level by level. At each level, we pair each node with an index representing its position assuming a complete binary tree. This allows us to compute the width of each level using the formula: width = last_index - first_index + 1. We then track the maximum width seen throughout the traversal. The use of indices handles cases where there are null gaps between nodes.

Code Solutions

# 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

from collections import deque

class Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        max_width = 0
        # Initialize queue with a tuple of (node, index)
        queue = deque([(root, 1)])
        
        while queue:
            level_length = len(queue)
            # Get the index of first node at current level
            _, first_index = queue[0]
            # Process nodes at current level
            for i in range(level_length):
                node, index = queue.popleft()
                # Check and add left child with index 2 * index
                if node.left:
                    queue.append((node.left, 2 * index))
                # Check and add right child with index 2 * index + 1
                if node.right:
                    queue.append((node.right, 2 * index + 1))
                # For the last node, calculate width of the level
                if i == level_length - 1:
                    current_width = index - first_index + 1
                    max_width = max(max_width, current_width)
        return max_width
← Back to All Questions