https://leetcode.com/problems/maximum-width-of-binary-tree/

maximum-width-of-binary-tree.go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type LevelNode struct {
    node *TreeNode
    level int
    order int
}

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

    queue := []*LevelNode{{
        node: root,
        level: 0,
        order: 0,
    }}
    
    var prevItem *LevelNode
    maxWidth := 0

    for len(queue) > 0 {
        item := queue[0]
        queue = queue[1:]
        
        if prevItem == nil || prevItem.level != item.level {
            prevItem = item
        }
        
        maxWidth = max(maxWidth, item.order - prevItem.order + 1)
        
        if item.node.Left != nil {
            queue = append(queue, &LevelNode{
                node: item.node.Left,
                level: item.level + 1,
                order: 2 * item.order + 1,
            })
        }
        
        if item.node.Right != nil {
            queue = append(queue, &LevelNode{
                node: item.node.Right,
                level: item.level + 1,
                order: 2 * item.order + 2,
            })
        }
    }
    
    return maxWidth
}

func max(a, b int) int {
    if a < b {
        return b
    }
    
    return a
}