Tree Width Calculation 0 based system

I was solving the classic problem of calculating the widest binary tree level - essentially finding the maximum width of in the tree. I had doubts around how left and right indices of nodes is calulated because I thought we use the standard formulas for calculating indices: left := 2i + 1 and right := 2i + 2, but it wasn't yielding the correct result.

Typically, if we want to calculate width in an array, we'd take the delta of start and end index. In a tree, it should be the same by assigning indices to each node, but here the width would be the number of nodes in that level: width = rightmost - leftmost + 1.
Okay, I get the concept, but then why aren't the typical left and right formulas working? I thought the standard formulas for left and right node indices in a tree are 2i+1 and 2i+2.
Then I understood...

The Key Insight: It's About Position, Not Traditional Indexing. The indexing formulas depend on what you're trying to achieve.

There are different systems:

Traditional Binary Heap Indexing Systems

System 1: 1 based indexing (starts from 1)

       1
    /     \
   2       3
  / \     / \
 4   5   6   7
 
Formulas:

Left child: 2*i
Right child: 2*i + 1

System 2: 0 based indexing (starts from 0)

       0
    /     \
   1       2
  / \     / \
 3   4   5   6

Formulas:

Left child: 2*i + 1
Right child: 2*i + 2

Reason for: Position Based Indexing for Width Calculation

A 0 based system specifically for width calculation would cause a problem. Here's why:
formulas (2i+1, 2i+2):

       0
    /     \
   1       2     <- indices 1, 2
  / \     / \
 3   4   5   6   <- indices 3, 4, 5, 6
 

Width calculation: rightmost - leftmost + 1 = 6 - 3 + 1 = 4
But Notice This Issue

       0
    /     \
   1       2
  /         \
 3           6   <- Gap! indices 3, 6 (missing 4, 5)

Width would be: 6 - 3 + 1 = 4 but actual width is only 2 nodes!
So, if we modify the solution
By using 2i and 2i+1, the code ensures consecutive indices at each level:

       0
    /     \
   0       1     <- 2*0=0, 2*0+1=1
  / \     / \
 0   1   2   3   <- 2*0=0, 2*0+1=1, 2*1=2, 2*1+1=3

This gives relative positioning within each level, making width calculation accurate even with gaps.

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

func widestBinaryTreeLevel(root *TreeNode) int {
	if root == nil {
		return 0
	}

	maxWidth := 0
	// queue stores (node, index) pairs
	queue := []struct {
		node  *TreeNode
		index int
	}{{root, 0}}

	for len(queue) > 0 {
		levelSize := len(queue)

		// Set leftmost_index to the index of the first node in this level
		leftmostIndex := queue[0].index
		rightmostIndex := leftmostIndex // Start at same point as leftmost

		// Process all nodes at the current level
		for i := 0; i < levelSize; i++ {
			nodeWithIndex := queue[0]
			queue = queue[1:] // popleft()

			node := nodeWithIndex.node
			index := nodeWithIndex.index

			if node.Left != nil {
				queue = append(queue, struct {
					node  *TreeNode
					index int
				}{node.Left, 2 * index}) // 2*i, not 2*i+1
			}
			if node.Right != nil {
				queue = append(queue, struct {
					node  *TreeNode
					index int
				}{node.Right, 2*index + 1}) // 2*i+1, not 2*i+2
			}

			rightmostIndex = index 
		}

		// Calculate width after processing entire level
		currentWidth := rightmostIndex - leftmostIndex + 1
		if currentWidth > maxWidth {
			maxWidth = currentWidth
		}
	}

	return maxWidth 
}