/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func printTree(root *TreeNode) [][]string {
	if root == nil {
		return [][]string{}
	}
	depth := 0
	helper(root, 0, &depth)
	res := make([][]string, depth)
	for i := range res {
		res[i] = make([]string, 1<<uint(depth)-1)
	}
	printer(root, len(res[0])/2, 0, 1<<uint(depth-2), res)
	return res
}

func printer(root *TreeNode, x, y, det int, res [][]string) {
	if root == nil {
		return
	}
	res[y][x] = strconv.Itoa(root.Val)
	printer(root.Left, x-det, y+1, det>>1, res)
	printer(root.Right, x+det, y+1, det>>1, res)
}

func helper(root *TreeNode, y int, depth *int) {
	if root == nil {
		return
	}
	y++
	if *depth < y {
		*depth = y
	}
	helper(root.Left, y, depth)
	helper(root.Right, y, depth)
}