package main

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedArrayToBST(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}
	mid := len(nums) / 2
	root := TreeNode{nums[mid], nil, nil}
	// only one element in nums, return TreeNode{ele, nil, nil}
	if mid == 0 {
		return &root
	}
	root.Left = sortedArrayToBST(nums[:mid])
	root.Right = sortedArrayToBST(nums[mid+1:])
	return &root
}

// func main() {
// 	t1 := sortedArrayToBST([]int{-10, -3, 0, 5, 9})
// 	printTree(t1)
// }