Sunday, March 5, 2023
Validate binary search tree
Go
- Time complexity: -
n
is a number of nodes - Auxiliary space: -
d
is a depth of a binary tree
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isValidBST(root *TreeNode) bool {
return checkWithMinMax(root, -1<<63, 1<<63-1)
}
func checkWithMinMax(root *TreeNode, left, right int) bool {
if root == nil {
return true
}
if root.Val >= right || root.Val <= left {
return false
}
isValidLeft := checkWithMinMax(root.Left, left, root.Val)
isValidRight := checkWithMinMax(root.Right, root.Val, right)
return isValidLeft && isValidRight
}