LeetCode 662: Maximum Width of Binary Tree Solution in Python – A Step-by-Step Guide

What Is LeetCode 662: Maximum Width of Binary Tree?

In LeetCode 662: Maximum Width of Binary Tree, you’re given the root of a binary tree (nodes with val, left, and right attributes), and your task is to find the maximum width across all levels. The width of a level is the number of nodes between the leftmost and rightmost non-null nodes, including any null nodes in between. Return this maximum width as an integer. For example, with root = [1, 3, 2, 5, 3, null, 9], the maximum width is 4 at level 2 (nodes 5 to 9, including nulls). This problem tests your ability to track node positions across tree levels efficiently.

Problem Statement

• Input:
• root: Root node of a binary tree.
• Output: An integer—maximum width of the tree.
• Rules:
• Width = number of nodes (including nulls) between leftmost and rightmost non-null nodes at a level.
• Compute for each level, return maximum.
• Tree may be incomplete or skewed.

Constraints

• Number of nodes: 1 to 3000.
• -100 ≤ Node.val ≤ 100.

Examples

• Input: root = [1, 3, 2, 5, 3, null, 9]
• Output: 4 (Level 2: 5 to 9, width = 4)
• Input: root = [1, 3, null, 5, 3]
• Output: 2 (Level 1: 3 to null, width = 2)
• Input: root = [1, 3, 2, 5]
• Output: 2 (Levels 1 and 2: width = 2)

These examples set the tree—let’s solve it!

Understanding the Problem: Measuring Width

To solve LeetCode 662: Maximum Width of Binary Tree in Python, we need to find the maximum width across all levels of a binary tree, counting nodes (including nulls) between the leftmost and rightmost non-null nodes at each level. A brute-force approach—listing all nodes per level and counting—would work but could be optimized. Since we need positions, we can use BFS or DFS with indexing. We’ll explore:

• Best Solution (BFS with Index Tracking): O(n) time, O(w) space—fast and intuitive (w = max width).
• Alternative Solution (DFS with Level Mapping): O(n) time, O(h) space—recursive but complex (h = height).

Let’s start with the BFS solution, breaking it down for beginners.

Best Solution: BFS with Index Tracking

Why This Is the Best Solution

The BFS with index tracking approach is the top choice for LeetCode 662 because it’s efficient—O(n) time with O(w) space—and uses breadth-first search to process levels sequentially, tracking node indices to compute widths directly. It fits constraints (n ≤ 3000) perfectly and is straightforward once you see the indexing pattern. It’s like measuring each level of the tree as you sweep across it!

How It Works

Think of this as a level measurer:

• Step 1: Initialize Queue:
• Use a queue with (node, index) pairs, root at index 0.
• Step 2: BFS by Level:
• For each level:
• Record leftmost index (first node).
• Process all nodes, enqueue children with indices:
• Left child: 2 * parent_index.
• Right child: 2 * parent_index + 1.
• Width = rightmost index - leftmost index + 1.
• Step 3: Track Maximum Width:
• Update max width per level.
• Step 4: Return Result:
• Return maximum width.

It’s like a width scanner—sweep and measure!

Step-by-Step Example

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

• Step 1: Queue = [(1, 0)], max_width = 0.
• Step 2: BFS:
• Level 0: [(1, 0)], width = 0-0+1 = 1, max_width = 1.
• Enqueue: (3, 0), (2, 1).
• Level 1: [(3, 0), (2, 1)], width = 1-0+1 = 2, max_width = 2.
• Enqueue: (5, 0), (3, 1), (9, 3).
• Level 2: [(5, 0), (3, 1), (9, 3)], width = 3-0+1 = 4, max_width = 4.
• Step 3: No deeper levels, max_width = 4.
• Output: 4.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codefrom collections import deque

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: TreeNode) -> int:
        # Step 1: Initialize queue and max width
        if not root:
            return 0
        queue = deque([(root, 0)])  # (node, index)
        max_width = 0

        # Step 2: BFS by level
        while queue:
            level_size = len(queue)
            leftmost = queue[0][1]  # First index of level

            # Process all nodes in current level
            for _ in range(level_size):
                node, index = queue.popleft()

                # Enqueue children with indices
                if node.left:
                    queue.append((node.left, 2 * index))
                if node.right:
                    queue.append((node.right, 2 * index + 1))

            # Compute width of this level
            rightmost = queue[-1][1] if queue else index
            width = rightmost - leftmost + 1
            max_width = max(max_width, width)

        # Step 3: Return maximum width
        return max_width

• Line 1: Import deque for queue.
• Lines 4-8: TreeNode class (standard).
• Lines 12-16: Init: Queue with root at index 0, max_width.
• Lines 19-33: BFS:
• Process level, track leftmost, enqueue children, compute width.
• Line 36: Return max_width.
• Time Complexity: O(n)—visit each node once.
• Space Complexity: O(w)—queue holds max width.

This is like a tree measurer—scan and count!

Alternative Solution: DFS with Level Mapping

Why an Alternative Approach?

The DFS with level mapping approach uses depth-first search—O(n) time, O(h) space (h = height). It’s more recursive, mapping each node’s index to its level, but requires extra bookkeeping to track widths. It’s like diving into the tree and measuring as you go!

How It Works

Picture this as a depth mapper:

• Step 1: Init level map:
• Dictionary to store leftmost index per level.
• Step 2: DFS:
• Recurse with (node, level, index).
• Update max width using leftmost and current index.
• Step 3: Return max width.

It’s like a depth counter—map and measure!

Step-by-Step Example

Example: Same as above

• Step 1: levels = {}, max_width = 0.
• Step 2: DFS:
• (1, 0, 0): levels[0]=0, width=1, max_width=1.
• (3, 1, 0): levels[1]=0, width=1, max_width=1.
• (5, 2, 0): levels[2]=0, width=1, max_width=1.
• (3, 2, 1): levels[2]=0, width=2-0+1=2, max_width=2.
• (9, 2, 3): levels[2]=0, width=4-0+1=4, max_width=4.
• (2, 1, 1): levels[1]=0, width=2-0+1=2, max_width=4.
• Step 3: Return 4.
• Output: 4.

Code for DFS Approach

Copy codeclass Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        # Step 1: Initialize level map and max width
        levels = {}  # Level -> leftmost index
        max_width = [0]  # Use list to modify in recursion

        # Step 2: DFS with index tracking
        def dfs(node, level, index):
            if not node:
                return

            # Record leftmost index for this level
            if level not in levels:
                levels[level] = index

            # Compute width at this level
            width = index - levels[level] + 1
            max_width[0] = max(max_width[0], width)

            # Recurse on children
            dfs(node.left, level + 1, 2 * index)
            dfs(node.right, level + 1, 2 * index + 1)

        dfs(root, 0, 0)

        # Step 3: Return maximum width
        return max_width[0]

• Lines 4-6: Init: Levels map, max_width as list.
• Lines 9-20: DFS:
• Set leftmost index, compute width, recurse with child indices.
• Line 23: Return max_width.
• Time Complexity: O(n)—visit each node once.
• Space Complexity: O(h)—recursion stack.

It’s a depth measurer—recurse and track!

Comparing the Two Solutions

• BFS (Best):
• Pros: O(n) time, O(w) space, level-wise clarity.
• Cons: Queue space for wide levels.
• DFS (Alternative):
• Pros: O(n) time, O(h) space, recursive elegance.
• Cons: Extra bookkeeping.

BFS wins for simplicity.

Additional Examples and Edge Cases

• Input: [1]
• Output: 1.
• Input: [1, 2, 3, 4, null, null, 5]
• Output: 2.

Both handle these well.

Complexity Breakdown

• BFS: Time O(n), Space O(w).
• DFS: Time O(n), Space O(h).

BFS is optimal for clarity.

Key Takeaways

• BFS: Level scanning—smart!
• DFS: Depth mapping—clear!
• Width: Trees are fun.
• Python Tip: Queues rock—see Python Basics.

Final Thoughts: Measure That Tree

LeetCode 662: Maximum Width of Binary Tree in Python is a fun tree challenge. BFS with index tracking offers speed and intuitiveness, while DFS provides a recursive alternative. Want more? Try LeetCode 102: Binary Tree Level Order Traversal or LeetCode 104: Maximum Depth of Binary Tree. Ready to measure? Head to Solve LeetCode 662 on LeetCode and find that width today!