Maximum Width of Binary Tree in DSA Go

Mental Model

We want to find the widest level in a tree by counting nodes between the leftmost and rightmost nodes at each level, including gaps.

Analogy: Imagine a tree as a family photo where some people stand far apart. The width is the distance between the leftmost and rightmost person in each row, counting empty spaces too.

       1
      / \
     3   2
    /     \
   5       9
  /         \
 6           7

Levels:
Level 0: 1
Level 1: 3 -> 2
Level 2: 5 -> null -> null -> 9
Level 3: 6 -> null -> null -> null -> null -> null -> null -> 7

Dry Run Walkthrough

Input: Binary tree with nodes: 1 (root), 3 (left child), 2 (right child), 5 (left child of 3), 9 (right child of 2), 6 (left child of 5), 7 (right child of 9)

Goal: Find the maximum width among all levels, counting null gaps between nodes

Step 1: Start level order traversal from root with index 0

Level 0: [(1,0)]

Why: We assign index 0 to root to track positions for width calculation

Step 2: Process level 0 nodes, enqueue children with indices: left child index = 2*0+1=1, right child index = 2*0+2=2

Level 1: [(3,1), (2,2)]

Why: Indexing children helps measure gaps between nodes

Step 3: Calculate width at level 0: last index 0 - first index 0 + 1 = 1

Max width so far: 1

Why: Width is distance between leftmost and rightmost nodes plus one

Step 4: Process level 1 nodes, enqueue children with indices: 3's left child (5) at 2*1+1=3, 2's right child (9) at 2*2+2=6

Level 2: [(5,3), (9,6)]

Why: We skip missing children to keep correct indices for gaps

Step 5: Calculate width at level 1: last index 2 - first index 1 + 1 = 2

Max width so far: 2

Why: Level 1 has two nodes with indices 1 and 2

Step 6: Process level 2 nodes, enqueue children: 5's left child (6) at 2*3+1=7, 9's right child (7) at 2*6+2=14

Level 3: [(6,7), (7,14)]

Why: Indices show large gap between nodes at this level

Step 7: Calculate width at level 2: last index 6 - first index 3 + 1 = 4

Max width so far: 4

Why: Width counts gaps between nodes including nulls

Step 8: Calculate width at level 3: last index 14 - first index 7 + 1 = 8

Max width so far: 8

Why: This is the widest level including null gaps

Result:

Maximum width is 8 at level 3
Level 3: 6 -> null -> null -> null -> null -> null -> null -> 7

Annotated Code

DSA Go

package main

import (
	"fmt"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func widthOfBinaryTree(root *TreeNode) int {
	if root == nil {
		return 0
	}
	type NodeIndex struct {
		node  *TreeNode
		index int
	}
	queue := []NodeIndex{{root, 0}}
	maxWidth := 0

	for len(queue) > 0 {
		levelLength := len(queue)
		startIndex := queue[0].index
		var endIndex int

		for i := 0; i < levelLength; i++ {
			current := queue[0]
			queue = queue[1:]
			// Normalize index to prevent overflow
			currIndex := current.index - startIndex

			if current.node.Left != nil {
				queue = append(queue, NodeIndex{current.node.Left, 2*currIndex + 1})
			}
			if current.node.Right != nil {
				queue = append(queue, NodeIndex{current.node.Right, 2*currIndex + 2})
			}

			if i == levelLength-1 {
				endIndex = currIndex
			}
		}

		width := endIndex + 1
		if width > maxWidth {
			maxWidth = width
		}
	}

	return maxWidth
}

func main() {
	// Construct the tree from dry run
	root := &TreeNode{Val: 1}
	root.Left = &TreeNode{Val: 3}
	root.Right = &TreeNode{Val: 2}
	root.Left.Left = &TreeNode{Val: 5}
	root.Right.Right = &TreeNode{Val: 9}
	root.Left.Left.Left = &TreeNode{Val: 6}
	root.Right.Right.Right = &TreeNode{Val: 7}

	fmt.Println(widthOfBinaryTree(root))
}

queue := []NodeIndex{{root, 0}}

Initialize queue with root node at index 0 to track positions

startIndex := queue[0].index

Record first index at current level to normalize indices and avoid overflow

currIndex := current.index - startIndex

Normalize current node index relative to startIndex for safe calculations

queue = append(queue, NodeIndex{current.node.Left, 2*currIndex + 1})

Assign left child index as 2*currIndex+1 to keep position tracking

queue = append(queue, NodeIndex{current.node.Right, 2*currIndex + 2})

Assign right child index as 2*currIndex+2 to keep position tracking

endIndex = currIndex

Update endIndex to last node's normalized index at this level

width := endIndex + 1

Calculate width as distance between first and last node plus one

if width > maxWidth { maxWidth = width }

Update maxWidth if current level's width is larger

Output

8

Complexity Analysis

Time: O(n) because we visit each node once during level order traversal

Space: O(n) because the queue can hold up to all nodes at the widest level

vs Alternative: Compared to naive approaches that might check each level separately without indexing, this method efficiently tracks positions to count gaps without extra tree traversals

Edge Cases

Empty tree

Returns 0 as width because there are no nodes

DSA Go

if root == nil { return 0 }

Tree with only root node

Returns 1 as width because only one node exists

DSA Go

queue := []NodeIndex{{root, 0}}

Tree with missing children causing gaps

Correctly counts width including null gaps using indexing

DSA Go

currIndex := current.index - startIndex

When to Use This Pattern

When a problem asks for the widest level in a tree including gaps, use level order traversal with position indexing to measure width efficiently.

Common Mistakes

Mistake: Not normalizing indices at each level causing integer overflow or incorrect width
Fix: Subtract startIndex from each node's index at the current level to keep indices small

Mistake: Counting only existing nodes without considering gaps between them
Fix: Use position indices to include null gaps in width calculation

Summary

Finds the maximum width of a binary tree by counting nodes and gaps at each level.

Use when you need to measure the widest level including empty spaces in a tree.

Track node positions with indices during level order traversal to count gaps correctly.