DSA sheet · Trees · BFS pattern (also solved with DFS)

Maximum Width of Binary Tree

This is the last question of the BFS pattern in the sheet. The tricky part isn't BFS. It's understanding what "width" means: width counts the empty spots between the two end nodes of a level, not just the nodes that exist. The teacher's tool for this is giving every node a position number (index), the way a heap numbers its slots. Along the way she explains why these numbers can get huge, how to keep them smaller, and how the same idea works with DFS. That indexing trick is the key takeaway.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part A · Maximum width with BFS (and the indexing idea)
• Part B · Maximum width with DFS
• Part C · Revision page

Part A · Maximum width with BFS

LeetCode 662

1The question in simple words

A level is one row of the tree (the root is level 0, its children level 1, and so on). The width of a level is the distance from its leftmost existing node to its rightmost existing node, counting every spot in between. Spots in between count even if they are empty, as if the tree were filled in completely. Return the largest width over all levels.

Our main example tree. Dots (·) are empty spots that lie between two real nodes:

               1
           /       \
          2         3
         / \       / \
        4   5     ·   6        level 2: 4, 5, (empty), 6  → width 4
       / \           /
      ·   7         8          level 3: 7 … 8             → width 6

• Level 0: just 1 → width 1.
• Level 1: 2 and 3 → width 2.
• Level 2: 4, 5, an empty spot (3 has no left child), and 6 → only 3 real nodes, but the width is 4.
• Level 3: the leftmost real node is 7, the rightmost is 8. Between them are 4 empty spots (the children of 5 and 3's missing left child) → width 6. The empty spot to the left of 7 (4's missing left child) is outside the two ends, so it doesn't count.

Answer: 6.

2What the constraints tell us

• Number of nodes: 1 to 3000 → the tree is never empty. (We keep a tiny None check anyway, it costs nothing.)
• Values: −100 to 100. We never add or multiply the values, so they can't overflow. But the index numbers we create can. That's the real constraint question here, covered in step 4.
• The answer is promised to fit in a 32-bit signed int. In Java the teacher casts the final width back to int for this reason. In Python we don't need to care.
• n ≤ 3000 → an O(n) solution is very fast.

3Intuition: give every spot a seat number

Picture a cinema with rows. Row k has 2^k seats. Every possible spot in a binary tree gets a seat number, whether someone sits there or not. Then:

width of a level = (seat number of the rightmost node) − (seat number of the leftmost node) + 1

The empty seats in between are counted automatically, because the numbers jump over them. Empty seats outside the two ends are never counted, because we only subtract the two end nodes.

4Building the logic from examples

Why not just count the nodes on each level?

Level 3 of our tree has only 2 real nodes (7 and 8), but its width is 6. Counting nodes gives the wrong answer. Width is about how many nodes could fit between the ends, not how many are actually there.

Why not push the None spots into the queue and count them?

Then we'd also store the useless empty spots outside the ends (like the one left of 7), and every None would add even more None children below it. A lot of wasted space, plus extra logic to trim the ends. Seat numbers give the same information with no extra entries.

Numbering method 1: the heap formula

The root gets index 0. If a node has index i:

• left child → 2i + 1
• right child → 2i + 2

               1 (0)
           /         \
        2 (1)        3 (2)
         / \          / \
     4 (3) 5 (4)   ·(5)  6 (6)
       / \               /
    ·(7)  7 (8)       8 (13)

The biggest width is NOT always on the last level

It's tempting to think "the bottom level is the widest, just measure that". The teacher shows why that's wrong. Change the tree so that only 6 has children on the last level:

               1
           /       \
          2         3
         / \         \
        4   5         6        level 2 → width 4
                     / \
                    8   9      level 3 → only 8, 9 next to each other → width 2

Now the answer is 4, from level 2. So we must measure every level and keep the maximum.

The constraint question: how big can the indexes get?

Index numbers grow with the number of levels, not the number of nodes. Every level doubles the numbers. Look at a tree that has nodes only on its two outer edges:

              1 (0)
            /       \
         2 (1)      3 (2)
          /            \
       4 (3)          5 (6)
        /                \
     6 (7)              7 (14)

Only 7 nodes, but the last index is already 14, and the width of the bottom level is 14 − 7 + 1 = 8. Add one more level on each edge (9 nodes) and the right index jumps to 30. Then 62 with 11 nodes, then 126 with 13 nodes… With h levels, the tree has room for 2^h − 1 spots, so the indexes go up to about 2^h.

(While building this example in the video, the teacher first miscounted the empty spots on the last level, stopped herself, and recounted: each spot on a level has two child spots below it, even the empty ones. That's why the numbering keeps doubling.)

Her reasoning about overflow: a full tree with about 3000 nodes has only about 11 or 12 levels (2¹¹ = 2048, 2¹² = 4096). So the indexes stay around a few thousand, which an int holds easily. If they went past 2³¹, a Java int would overflow and we'd need a long. She uses long anyway, to be safe.

Numbering method 2: start every level from 0 (the teacher's improvement)

With method 1, level 1 starts at 1, level 2 at 3, level 3 at 7… Each level starts at a big number. The teacher's observation: use

• root → 0
• left child → 2i
• right child → 2i + 1

Now every level's seats run from 0 to 2^k − 1. The numbers are smaller (about half the size), but the widths stay exactly the same, because the whole level just shifted left by the same amount.

               1 (0)
           /         \
        2 (0)        3 (1)
         / \          / \
     4 (0) 5 (1)   ·(2)  6 (3)
       / \               /
    ·(0)  7 (1)       8 (6)

Every level in method 2 is method 1 minus (2^k − 1). It's the same picture, just with smaller labels. We use method 2 from now on.

Storing the index in BFS: pairs in the queue

A queue entry normally holds just a node. Now we need the node and its index, so we push a pair (node, index). (Java needs a small Pair class. In Python a tuple is enough.)

Getting the first and last index of each level

• first: before popping anything on this level, peek at the front of the queue: queue[0][1]. The front is the leftmost node of the level.
• last: as we pop each node, overwrite last with its index. After the level's last pop, last holds the rightmost index.

After the level: max_width = max(max_width, last - first + 1).

5Approach steps

1. Push (root, 0) into a queue. Set max_width = 0.
2. While the queue isn't empty: size = len(queue), first = queue[0][1].
3. Pop size pairs. For each, set last = index.
4. Push the left child with 2*index and the right child with 2*index + 1 (if they exist).
5. After the level: max_width = max(max_width, last - first + 1).
6. Return max_width.

6Code (Python)

from collections import deque

class Solution:
    def widthOfBinaryTree(self, root):
        if root is None:
            return 0
        max_width = 0
        queue = deque([(root, 0)])         # (node, index) pairs
        while queue:
            size = len(queue)
            first = queue[0][1]            # peek: leftmost index of this level
            last = first
            for _ in range(size):
                node, idx = queue.popleft()
                last = idx                 # keeps moving right
                if node.left:
                    queue.append((node.left, 2 * idx))
                if node.right:
                    queue.append((node.right, 2 * idx + 1))
            max_width = max(max_width, last - first + 1)
        return max_width

from collections import deque

class Solution:
    def widthOfBinaryTree(self, root):
        if root is None:
            return 0
        max_width = 0
        queue = deque([(root, 0)])
        while queue:
            size = len(queue)
            first = queue[0][1]
            last = 0
            for _ in range(size):
                node, idx = queue.popleft()
                idx = idx - first          # shift: this level now starts at 0
                last = idx
                if node.left:
                    queue.append((node.left, 2 * idx))
                if node.right:
                    queue.append((node.right, 2 * idx + 1))
            max_width = max(max_width, last + 1)   # first is 0 after the shift
        return max_width

The second version keeps every index below 2 × (width of the previous level), so it never overflows in any language. In Python both are correct.

7Code line by line

8Dry run: watch the queue

The teacher's small example (answer 4). Pairs are written as value:index.

        1 (0)
       /    \
    2 (0)   3 (1)
     /         \
  4 (0)       5 (3)

On the main example tree, the four levels give widths 1, 2, 4, 6, so the answer is 6. On the changed tree (8 and 9 under 6), the widths are 1, 2, 4, 2, so the answer is 4.

9Complexity & remember

• Time O(n): each node is pushed and popped once, with O(1) work each.
• Space O(n): the queue holds up to one full level of pairs.

Part B · Maximum width with DFS

1The question in simple words

Same problem, same seat numbers (2i, 2i + 1). Now we walk depth first.

2What the constraints tell us

Same as Part A. The tree can be up to 3000 levels deep (a chain), so the recursion can go 3000 calls deep. Python's default limit is 1000, so on LeetCode's biggest tests the DFS version may need sys.setrecursionlimit. BFS has no such issue.

3Intuition: what's missing in DFS

In BFS, the whole level sits in the queue at once, so its first and last index are right there. In DFS, when we stand at a node, we have not seen the rest of its level yet. Some of it is still to the right, waiting to be visited. So we need a memory: for each level, remember the index of the first (leftmost) node we met there. Later, every node on that level can measure its distance from that first node.

4Building the logic

A list of first indexes, one per level

Keep a list first, where first[level] = the index of the leftmost node on that level. When do we fill it? The same trick as DFS level order traversal: if level == len(first), this level has never been visited before → this node is the first one we've reached here → append its index.

Measure the width at every node

At every node, compute idx - first[level] + 1. That's the width from the level's left end up to this node. When we reach the rightmost node of the level, this gives the full width of the level. We don't know which node is the rightmost, so we just measure at every node and keep the maximum. A larger index always gives a larger value, so the true rightmost always wins.

Why we can't assume the first index is 0

With 2i / 2i + 1 numbering, a full level starts at index 0. But if the leftmost spot is empty, the level starts somewhere else. In our main tree, level 3's leftmost spot (4's left child) is empty, so the first real node is 7 at index 1. If we pretended it was 0, we would get 6 − 0 + 1 = 7 for node 8, which is wrong. The correct value is 6 − 1 + 1 = 6. That's exactly why the teacher stores the real first index for each level.

Recurse

Go left with (level + 1, 2*idx), then right with (level + 1, 2*idx + 1). The order matters: left must be first, so that the first-index rule above stays true.

5Approach steps

1. Create an empty list first and set max_width = 0.
2. Call dfs(root, level=0, idx=0).
3. In dfs: if node is None → return.
4. If level == len(first) → first.append(idx).
5. max_width = max(max_width, idx - first[level] + 1).
6. Recurse left with 2*idx, then right with 2*idx + 1, both at level + 1.

6Code (Python)

class Solution:
    def widthOfBinaryTree(self, root):
        self.first = []          # first[level] = index of the leftmost node
        self.max_width = 0
        self.dfs(root, 0, 0)
        return self.max_width

    def dfs(self, root, level, idx):
        if root is None:
            return
        if level == len(self.first):         # first visit to this level
            self.first.append(idx)
        width = idx - self.first[level] + 1  # distance from the left end
        self.max_width = max(self.max_width, width)
        self.dfs(root.left, level + 1, 2 * idx)        # left first!
        self.dfs(root.right, level + 1, 2 * idx + 1)

7Code line by line

8Dry run using the call stack

Main tree, method 2 numbers. Calls are written as (value, level, index).

               1 (0)
           /         \
        2 (0)        3 (1)
         / \            \
     4 (0) 5 (1)        6 (3)
         \              /
         7 (1)       8 (6)

Final answer: 6, the same as BFS. Row 9 is where the stored first index (1, not 0) matters.

9Complexity, BFS vs DFS & remember

• Time O(n): every node is visited once.
• Space O(height): the call stack, plus the first list (one entry per level). For a balanced tree that's about log n. For a skewed tree (one long chain) it is O(n).

Which is better? Both are linear. The teacher prefers BFS here: the queue already holds each whole level, so we get the first and last index for free. DFS needs the extra first list and has to carry the level along in every call.

Part C · Revision page

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

main = TreeNode(1, TreeNode(2, TreeNode(4, None, TreeNode(7)), TreeNode(5)),
                   TreeNode(3, None, TreeNode(6, TreeNode(8))))
changed = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)),
                      TreeNode(3, None, TreeNode(6, TreeNode(8), TreeNode(9))))
small = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3, None, TreeNode(5)))
s = Solution()
print(s.widthOfBinaryTree(main))      # 6
print(s.widthOfBinaryTree(changed))   # 4
print(s.widthOfBinaryTree(small))     # 4
print(s.widthOfBinaryTree(TreeNode(1)))  # 1

Based on this video: Maximum Width of Binary Tree | BFS & DFS