⚡Flashcard Drill➔
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

  1. Assign each node a position index as in a heap: the left child is 2i and the right child 2i + 1, with the root at 0.
  2. The width of a level is last_index - first_index + 1, where the indices include the implicit nulls.
  3. A level-order traversal with a frozen level size gives the first and last indices directly.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems