package algoexpert.medium;

/*
PROBLEM:
Validate a BST

Solution:
1. Recursion : t: O(n) | s: O(n)
*/


public class ValidateBST {

    static class BST
    {
        public int value;
        public BST left;
        public BST right;

        public BST(int value) {
            this.value = value;
        }
    }

    // t: O(n) | s: O(n)
    public static boolean validator(BST tree, int min, int max)
    {
        if (tree == null) { return true; }

        if (tree.value < min || tree.value >= max)
        { return false; }

        return validator(tree.left, min, tree.value)
                && validator(tree.right, tree.value, max);
    }

    public static boolean validateBst(BST tree)
    {
        return validator(tree.left, Integer.MIN_VALUE, tree.value)
                && validator(tree.right, tree.value, Integer.MAX_VALUE);
    }

}