package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
	isValid, _, _ := isValidBSTRoot(root)
	return isValid
}

func isValidBSTRoot(root *TreeNode) (isValid bool, min int, max int) {
	if root == nil {
		isValid = true
		return // Do NOT rely on math.MaxInt32 or so
	}
	isValidL, minL, maxL := isValidBSTRoot(root.Left)
	if root.Left == nil {
		min = root.Val
	} else {
		if !isValidL || root.Val <= maxL {
			return
		}
		min = minL
	}
	isValidR, minR, maxR := isValidBSTRoot(root.Right)
	if root.Right == nil {
		max = root.Val
	} else {
		if !isValidR || root.Val >= minR {
			return
		}
		max = maxR
	}
	isValid = true
	return
}

// func main() {
// 	//    1
// 	//   / \
// 	// nil  2
// 	//     / \
// 	//    3  nil
// 	n3 := TreeNode{3, nil, nil}
// 	n2 := TreeNode{2, &n3, nil}
// 	n1 := TreeNode{1, nil, &n2}
// 	fmt.Println(isValidBST(&n1))
// 	// nil
// 	fmt.Println(isValidBST(nil))
// 	// 2147483647
// 	fmt.Println(isValidBST(&TreeNode{math.MaxInt32, nil, nil}))
// 	//    1
// 	//   / \
// 	// nil  1
// 	n6 := TreeNode{1, nil, nil}
// 	n5 := TreeNode{1, nil, &n6}
// 	fmt.Println(isValidBST(&n5))
// }