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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Width of Binary Tree

Difficulty: Medium

Problem Description

Given the root of a binary tree, return the maximum width of the given tree. The maximum width of a 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 that would be present in a complete binary tree extending down to that level are also counted into the length calculation.

Key Insights

  • The width of a level in a binary tree is determined by the positions of the leftmost and rightmost non-null nodes at that level.
  • To compute the maximum width, we need to traverse the tree level by level (BFS approach), keeping track of the indices of nodes to calculate the width.
  • The use of a queue data structure allows us to efficiently manage the nodes at each level while calculating their positions.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the binary tree, as we visit each node once. Space Complexity: O(w), where w is the maximum width of the binary tree, which is the space required to store the nodes at the current level in the queue.

Solution

To solve the problem, we can use a breadth-first search (BFS) approach. We will utilize a queue to keep track of the nodes at each level, along with their corresponding indices. The width of each level can be calculated by finding the difference between the indices of the leftmost and rightmost nodes. We will update the maximum width as we traverse each level.

Code Solutions

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def widthOfBinaryTree(root):
    if not root:
        return 0
    
    max_width = 0
    queue = deque([(root, 0)])  # queue holds pairs of (node, index)
    
    while queue:
        level_length = len(queue)
        _, first_index = queue[0]  # index of the first node at this level
        for i in range(level_length):
            node, index = queue.popleft()
            if node.left:
                queue.append((node.left, 2 * index))  # left child index
            if node.right:
                queue.append((node.right, 2 * index + 1))  # right child index
        # width of the current level is index of last node - index of first node + 1
        max_width = max(max_width, index - first_index + 1)
    
    return max_width
← Back to All Questions