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.

Practice

1. What does the "maximum width" of a binary tree represent?

easy

A. The sum of values of all nodes at the widest level

B. The height of the tree from root to the deepest leaf

C. The total number of nodes in the tree

D. The largest number of nodes present at any single level of the tree

Solution

1. Step 1: Understand the definition of width in a binary tree

   The width is the count of nodes at a particular level in the tree.

2. Step 2: Identify maximum width

   The maximum width is the largest such count among all levels.

3. Final Answer:

   The largest number of nodes present at any single level of the tree -> Option D

4. Quick Check:

   Maximum width = max nodes at any level [OK]

Hint: Width means count of nodes at one level, not height or sum [OK]

Common Mistakes:

• Confusing width with height of the tree
• Thinking width is sum of node values
• Counting total nodes instead of per level

2. Which Go data structure is best suited to track nodes level by level when finding maximum width of a binary tree?

easy

A. Queue

B. Stack

C. Map

D. Slice

Solution

1. Step 1: Identify traversal method for level order

   Level order traversal requires processing nodes level by level, which is done using a queue.

2. Step 2: Choose data structure

   A queue allows nodes to be added at the end and removed from the front, perfect for breadth-first traversal.

3. Final Answer:

   Queue -> Option A

4. Quick Check:

   Level order traversal uses queue [OK]

Hint: Use queue for level order traversal to measure width [OK]

Common Mistakes:

• Using stack which is LIFO, not suitable for level order
• Using map which doesn't preserve order
• Using slice without queue operations

3. What is the output of the following Go code snippet that calculates maximum width of a binary tree?

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

func maxWidth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    queue := []*TreeNode{root}
    maxWidth := 0
    for len(queue) > 0 {
        levelSize := len(queue)
        if levelSize > maxWidth {
            maxWidth = levelSize
        }
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    return maxWidth
}

root := &TreeNode{Val: 1}
root.Left = &TreeNode{Val: 2}
root.Right = &TreeNode{Val: 3}
root.Left.Left = &TreeNode{Val: 4}
root.Right.Right = &TreeNode{Val: 5}

fmt.Println(maxWidth(root))

medium

A. 3

B. 2

C. 4

D. 5

Solution

1. Step 1: Analyze tree structure and levels

   Level 1: Node 1 (1 node), Level 2: Nodes 2 and 3 (2 nodes), Level 3: Nodes 4 and 5 (2 nodes)

2. Step 2: Calculate maximum width

   Maximum width is the largest number of nodes at any level, which is 2.

3. Step 3: Re-examine the tree structure carefully

   Actually, at Level 3, nodes are 4 and 5 (2 nodes), but at Level 2, nodes are 2 and 3 (2 nodes), so max width is 2. However, the code counts the queue size before processing children, so at Level 1 queue size is 1, Level 2 queue size is 2, Level 3 queue size is 2. The maximum width is 2.

4. Step 4: Check if any level has 3 nodes

   No level has 3 nodes, so 3 (3) is incorrect.

5. Final Answer:

   2 -> Option B

6. Quick Check:

   Max nodes at any level = 2 [OK]

Hint: Count nodes per level carefully to find max width [OK]

Common Mistakes:

• Counting total nodes instead of per level
• Miscounting nodes at last level
• Assuming root level has more nodes

4. Identify the bug in this Go code snippet that attempts to find the maximum width of a binary tree:

func maxWidth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    queue := []*TreeNode{root}
    maxWidth := 0
    for len(queue) > 0 {
        levelSize := len(queue)
        if levelSize > maxWidth {
            maxWidth = levelSize
        }
        for i := 0; i <= levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    return maxWidth
}

medium

A. The inner loop condition should be i < levelSize, not i <= levelSize

B. The queue should be initialized empty, not with root

C. The maxWidth should be updated after the inner loop

D. The function should return maxWidth + 1

Solution

1. Step 1: Check loop boundaries for processing nodes

   The inner loop runs from i = 0 to i <= levelSize, which means it runs levelSize + 1 times, causing out-of-range error.

2. Step 2: Correct loop condition

   The loop should run exactly levelSize times, so condition must be i < levelSize.

3. Final Answer:

   The inner loop condition should be i < levelSize, not i <= levelSize -> Option A

4. Quick Check:

   Loop runs one extra time causing error [OK]

Hint: Use < for loops when iterating fixed count [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Initializing queue incorrectly
• Updating maxWidth at wrong time

5. Given a binary tree where some nodes are missing children, how can you modify the maximum width calculation to include the 'null' positions between nodes, effectively measuring the width as the distance between the leftmost and rightmost non-null nodes at each level? Choose the best approach to implement this in Go.

hard

A. Use recursion to count nodes and ignore null gaps

B. Count only non-null nodes per level ignoring positions

C. Use a queue storing pairs of (node, index) where index represents position, and calculate width as max index difference per level

D. Calculate width as total nodes in tree divided by height

Solution

1. Step 1: Understand the problem of null gaps

   Normal width counts nodes only, but to include gaps, we track positions of nodes as if tree was complete.

2. Step 2: Use index tracking with queue

   Store each node with an index representing its position. For each level, width = last index - first index + 1.

3. Step 3: Implement with queue of (node, index) pairs

   This approach allows measuring width including null gaps between nodes.

4. Final Answer:

   Use a queue storing pairs of (node, index) where index represents position, and calculate width as max index difference per level -> Option C

5. Quick Check:

   Index tracking captures null gaps in width [OK]

Hint: Track node positions with indices to include gaps [OK]

Common Mistakes:

• Ignoring null gaps by counting only nodes
• Using recursion without position tracking
• Calculating width as total nodes divided by height