Is Maximum Width of Binary Tree easy or hard?

Maximum Width of Binary Tree is considered a medium-level problem. The tree traversal itself is straightforward, but the challenge comes from correctly tracking positions to account for gaps between nodes.

Maximum Width of Binary Tree Python/Java solution

Both Python and Java implementations typically use a queue storing pairs of (node, index). For each level, track the first and last index and update the maximum width. The same indexing logic works across languages and maintains O(n) time complexity.

How to solve Maximum Width of Binary Tree in O(n)?

Traverse the tree while assigning indices that mimic a complete binary tree layout. During BFS, track the first and last index at each level and compute width using their difference. Because every node is processed once, the algorithm achieves O(n) time complexity.

What is the best approach for Maximum Width of Binary Tree?

The most common solution uses level order traversal (BFS) with positional indexing. Each node is assigned an index similar to a complete binary tree representation, allowing you to compute width as last_index - first_index + 1 for each level. This approach runs in O(n) time and O(n) space.

Is Maximum Width of Binary Tree asked at Google/Amazon/Meta?

Binary tree traversal and width-related problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variations of this problem test understanding of BFS, DFS, and how tree nodes map to array-style indexing.

What data structure is used in Maximum Width of Binary Tree?

The main data structure is a queue for breadth-first traversal. Each queue entry stores a tree node along with its positional index. In the DFS version, recursion and a hash map or array store the first index encountered at each depth.

What is the time complexity of Maximum Width of Binary Tree?

The optimal solutions run in O(n) time where n is the number of nodes in the tree. Each node is visited exactly once during traversal. Space complexity is O(n) for the BFS queue or O(h) for the DFS recursion stack, where h is the height of the tree.

Description Solution Video 22:41

662. Maximum Width of Binary Tree

Medium46.0% acceptance8 companies

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.

It is guaranteed that the answer will in the range of a 32-bit signed integer.

Example 1:

Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: 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
Explanation: 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
Explanation: 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

Asked at 8 companies

Flipkart Bytedance Amazon

Google Bloomberg Tiktok Microsoft Meta

Topics

22:41

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
9        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1,3,2,5,3,null,9]

Input

[1,3,2,5,null,null,9,6,null,7]

Input

[1,3,2,5]

Your code is saved on this device.Solution