Maximum Width of Binary Tree in DSA Go - Execution Trace

Concept Flow - Maximum Width of Binary Tree

Start at root node

↓

Initialize queue with root and index 0

↓

While queue not empty

↓

For each level: get first and last node indices

↓

Calculate width = last_index - first_index + 1

↓

Update max width if current width is larger

↓

Add children to queue with updated indices

↓

Repeat for next level

↓

Return max width found

We start from the root, use a queue to track nodes level by level with indices, calculate width per level, update max width, and continue until all levels are processed.

Execution Sample

DSA Go

func widthOfBinaryTree(root *TreeNode) int {
    maxWidth := 0
    queue := []struct{node *TreeNode; index int}{{root, 0}}
    for len(queue) > 0 {
        levelLen := len(queue)
        startIndex := queue[0].index
        endIndex := queue[levelLen-1].index
        width := endIndex - startIndex + 1
        if width > maxWidth {
            maxWidth = width
        }
        for i := 0; i < levelLen; i++ {
            curr := queue[0]
            queue = queue[1:]
            if curr.node.Left != nil {
                queue = append(queue, struct{node *TreeNode; index int}{curr.node.Left, 2 * curr.index + 1})
            }
            if curr.node.Right != nil {
                queue = append(queue, struct{node *TreeNode; index int}{curr.node.Right, 2 * curr.index + 2})
            }
        }
    }
    return maxWidth
}

This code finds the maximum width of a binary tree by tracking node indices at each level using a queue.

Execution Table

Step	Operation	Nodes in Queue (node val:index)	Level Length	Start Index	End Index	Width Calculated	Max Width	Visual Tree State
1	Initialize queue with root	[1:0]	1	0	0	1	1	Level 0: 1(0)
2	Process level 0	[1:0]	1	0	0	1	1	Level 0 processed, enqueue children 2:1, 3:2
3	Process level 1	[2:1, 3:2]	2	1	2	2	2	Level 1 processed, enqueue children 4:3, 5:4, 6:5
4	Process level 2	[4:3, 5:4, 6:5]	3	3	5	3	3	Level 2 processed, enqueue child 7:9
5	Process level 3	[7:9]	1	9	9	1	3	Level 3 processed, no children
6	Queue empty, end	[]	0	-	-	-	3	Traversal complete, max width = 3

💡 Queue is empty, all levels processed, maximum width found is 3

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
maxWidth	0	1	2	3	3	3	3
queue	[(1,0)]	[(2,1),(3,2)]	[(4,3),(5,4),(6,5)]	[(7,9)]	[]	[]	[]

Key Moments - 3 Insights

Why do we assign indices like 2*index+1 and 2*index+2 to child nodes?

Assigning indices this way simulates the position of nodes in a full binary tree, allowing us to calculate width by subtracting the first and last indices at each level (see execution_table rows 2-4).

Why do we subtract startIndex from endIndex and add 1 to get width?

Because indices start at 0, width is the count of positions between start and end inclusive, so width = endIndex - startIndex + 1 (see execution_table columns Width Calculated).

What happens if the tree is skewed and some nodes are missing?

The indexing still accounts for missing nodes by skipping indices, so width reflects the maximum gap including nulls (see how indices jump in execution_table rows 3 and 4).

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the width calculated for that level?

A 2

B 3

C 1

D 4

💡 Hint

Check the 'Width Calculated' column at Step 3 in the execution_table

At which step does the maxWidth first update to 3?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Max Width' column in execution_table and find when it changes to 3

If the root had no children, what would be the maxWidth returned?

A 0

B 1

C 2

D Undefined

💡 Hint

Refer to variable_tracker and execution_table Step 1 where only root node is present

Concept Snapshot

Maximum Width of Binary Tree:
- Use BFS level order traversal with a queue
- Assign indices to nodes: left = 2*index+1, right = 2*index+2
- Width at level = last_index - first_index + 1
- Track max width across all levels
- Return max width after traversal

Full Transcript

To find the maximum width of a binary tree, we start at the root and use a queue to traverse level by level. Each node is assigned an index representing its position if the tree were complete. For each level, we calculate the width by subtracting the first node's index from the last node's index and adding one. We update the maximum width found so far if the current level's width is larger. We continue until all levels are processed and then return the maximum width. This method accounts for missing nodes by using indices that reflect their positions in a full binary tree.