#662

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Maximum Width of Binary Tree

Determine the maximum width of a binary tree by calculating the width of each level and considering the positions of the nodes.

tree depth first search breadth first search binary tree

Problem Statement

Given a binary tree, your task is to find the maximum width of the tree. The width is determined by the longest distance between non-null nodes on the same level, accounting for the null nodes between the end nodes of a level.

A level's width is defined as the distance between the leftmost and rightmost non-null nodes at that level. The width calculation includes any null nodes that would exist in a complete binary tree, ensuring that even gaps between nodes are counted.

Examples

Example 1

Input: root = [1,3,2,5,3,null,9]

Output: 4

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

Example 2

Input: root = [1,3,2,5,null,null,9,6,null,7]

Output: 7

The maximum width exists in the fourth level with length 7 (6,null,null,null,null,null,7).

Example 3

Input: root = [1,3,2,5]

Output: 2

The maximum width exists in the second level with length 2 (3,2).

Constraints

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

Solution Approach

Level-order Traversal

To find the maximum width, use a level-order traversal, often implemented with a queue. During traversal, track the position of each node at its level. The width can be calculated by the difference between the positions of the leftmost and rightmost nodes at each level.

Index Tracking for Positioning

For efficient width calculation, maintain a unique index for each node in the level. When processing nodes at a particular level, compute the width as the difference between the indices of the first and last non-null nodes, including any null nodes between them.

Handling Sparse Nodes

Ensure that the null nodes are considered in the width calculation by using the properties of a complete binary tree. Track missing children to maintain accurate indices and properly calculate the width, even for sparse trees.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of nodes processed during the traversal, typically O(n) where n is the number of nodes. Space complexity is O(n) due to the queue used for level-order traversal, which holds the nodes at each level.

What Interviewers Usually Probe

Checks if the candidate can effectively apply breadth-first search (BFS) in a tree problem.
Assesses understanding of level-order traversal and index tracking.
Evaluates the ability to handle edge cases like sparse trees or deep binary trees.

Common Pitfalls or Variants

Common pitfalls

Not accounting for null nodes between the non-null nodes at each level.
Misunderstanding the problem by only counting nodes, instead of considering positions in a complete binary tree.
Failing to maintain accurate indices when nodes are missing on a level, which may lead to incorrect width calculations.

Follow-up variants

Calculate the width of a binary tree with missing nodes, ensuring that null nodes are counted in the width.
Solve this problem with an iterative approach using a queue, rather than a recursive one.
Optimize the space complexity by using alternative data structures or modifying the traversal approach.

FAQ

What is the maximum width of binary tree problem?

The problem asks to find the maximum width of a binary tree, defined as the maximum distance between the leftmost and rightmost non-null nodes at any level.

How do you solve the Maximum Width of Binary Tree problem?

You can solve this by performing a level-order traversal and calculating the width by tracking the leftmost and rightmost non-null node indices at each level.

What are the main algorithms to use for solving the Maximum Width of Binary Tree?

Breadth-First Search (BFS) or Depth-First Search (DFS) with a level-tracking mechanism are the most effective algorithms for this problem.

What common mistakes should I avoid while solving the Maximum Width of Binary Tree?

Avoid overlooking null nodes or not properly handling index calculations for missing nodes, both of which can lead to incorrect width results.

How can GhostInterview help me solve the Maximum Width of Binary Tree problem?

GhostInterview offers step-by-step guidance on BFS traversal, highlights key pitfalls, and provides practice problems to solidify understanding of width calculations.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# 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
class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        ans = 0
        q = deque([(root, 1)])
        while q:
            ans = max(ans, q[-1][1] - q[0][1] + 1)
            for _ in range(len(q)):
                root, i = q.popleft()
                if root.left:
                    q.append((root.left, i << 1))
                if root.right:
                    q.append((root.right, i << 1 | 1))
        return ans

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# 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
class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        ans = 0
        q = deque([(root, 1)])
        while q:
            ans = max(ans, q[-1][1] - q[0][1] + 1)
            for _ in range(len(q)):
                root, i = q.popleft()
                if root.left:
                    q.append((root.left, i << 1))
                if root.right:
                    q.append((root.right, i << 1 | 1))
        return ans

Continue Practicing

#655 print binary tree #653 two sum iv input is a bst #637 average of levels in binary tree