NeetCode #439LC-662MediumTrees
← Back to All Problems#439 · #662 · Maximum Width of Binary Tree(二叉树最大宽度)
📌 Problem Statement & Constraints
Given the root of a binary tree, return the maximum width of the tree: the maximum number of nodes between the leftmost and rightmost non-null nodes of any level, counting the nulls in between as if the tree were a complete tree. Constraints: the number of nodes is in
[1, 3000], -100 <= Node.val <= 100.💡 Core Algorithmic Approaches
- Assign each node a position index as in a heap: the left child is
2iand the right child2i + 1, with the root at 0. - The width of a level is
last_index - first_index + 1, where the indices include the implicit nulls. - A level-order traversal with a frozen level size gives the first and last indices directly.
- Important: the indices grow exponentially with depth, so subtract each level's first index (or use Python's unbounded integers, which handle it but waste memory).
💻 Benchmark Python3 Implementation
class Solution:
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
from collections import deque
q = deque([(root, 0)]) # (node, heap-style index)
best = 0
while q:
n = len(q)
first = q[0][1]
last = q[-1][1]
best = max(best, last - first + 1)
base = first # normalise to keep indices small
for _ in range(n):
node, i = q.popleft()
i -= base
if node.left:
q.append((node.left, 2 * i))
if node.right:
q.append((node.right, 2 * i + 1))
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each node is enqueued and dequeued once.
💾 Space Complexity
O(w) for the widest level.
⚠️ Interview Pitfalls & Follow-ups
- Counting only the actual nodes: the width includes the null gaps, which is why heap-style indices are used.
- Skipping the index normalisation: for a skewed tree the indices double every level, so a depth-3000 tree would need astronomically large integers.
- Using a DFS without tracking positions: the width is a per-level property.
- Assuming the tree is complete: the width is measured on the virtual complete tree, not the actual one.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.