package main

import (
	"fmt"
)

// print tree
func printTree(root *TreeNode) {
	if root == nil {
		return
	}
	fmt.Print(root.Val, " ")
	if root.Left != nil {
		printTree(root.Left)
	}
	if root.Right != nil {
		printTree(root.Right)
	}
}

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)
}