https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/

verticalOrderTraversal.go

// Entry in our intermediate result
type Entry struct {
	pos  int
	vals []int
}

// Entries is just a list of Entry-ies
type Entries []Entry

func (e Entries) Len() int {
	return len(e)
}

func (e Entries) Less(i, j int) bool {
	return e[i].pos < e[j].pos
}

func (e Entries) Swap(i, j int) {
	e[i], e[j] = e[j], e[i]
}

func iot(node *TreeNode, dist int, m map[int][]int) {

	if node == nil {
		return
	}

	iot(node.Left, dist-1, m)

	list, exists := m[dist]
	if !exists {
		m[dist] = []int{node.Val}
	} else {
		m[dist] = append(list, node.Val)
	}

	iot(node.Right, dist+1, m)
}

func verticalTraversal(root *TreeNode) [][]int {

	m := make(map[int][]int)

	iot(root, 0, m)

	// covert map into array of structs
	entries := make(Entries, 0)
	for key, vals := range m {
		entries = append(entries, Entry{key, vals})
	}

	sort.Sort(entries)

	result := make([][]int, len(entries))
	for i := 0; i < len(entries); i++ {
		result[i] = entries[i].vals
	}
	return result
}