// MARK: - 98 Validate Binary Search Tree

// Бинарное дерево - это такое дерево, у которого
// 1) Правый ребенок и ВСЕ его элементы больше родителя
// 2) Левый ребенок и все его дети меньше родителя

// Вот мы так идем и проверяем границы для каждого узла: для самого родителя (-беск < node < +беск)
// Идем ниже и изменяем интервал в зависимости от того какой ребенок

// left и right это значения с которыми сравниваем значение узла

func isValidBST(_ root: TreeNode?) -> Bool {

    // Это будет рекурсивная функция, поэтому пропишем базовый случай
    func valid(node: TreeNode?, left: Int, right: Int) -> Bool {

        // если дошли до конца и раньше не вышли значит все ок
        if node == nil {
            return true
        }

        if !(node!.val < right && node!.val > left) {
            return false
        }

        // Делаем рекурсивный вызов - для левого и правого ребенка - если хотя бы одна вернула false - возвращаем false
        return valid(node: node!.left, left: left, right: node!.val) && valid(node: node!.right, left: node!.val, right: right)
    }
    return valid(node: root, left: -Int.max, right: Int.max)
}





public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}