/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func widthOfBinaryTree(root *TreeNode) int {
	m := make(map[int][]int)
	helper(root, 0, 0, m)
	max := 0
	for _, v := range m {
		max = maxInt(max, v[1]-v[0])
	}
	return max + 1
}

func helper(root *TreeNode, x, y int, m map[int][]int) {
	if root == nil {
		return
	}
	if v, ok := m[y]; ok {
		v[0] = minInt(v[0], x)
		v[1] = maxInt(v[1], x)
	} else {
		m[y] = []int{x, x}
	}
	helper(root.Left, x<<1, y+1, m)
	helper(root.Right, (x<<1)|1, y+1, m)
}

func minInt(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func maxInt(x, y int) int {
	if x < y {
		return y
	}
	return x
}