/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    // This type of solution works when root->left <= root->val <= root->right
    // This solution does not work when root->left < root->val < root->right
    // It will fail if some nodes have as value 2^16 or -2^16
    /*
    bool isBST(TreeNode* root, int min, int max) {

        if (!root)
            return true;

        bool isCurrent = root->val > min && root->val < max;
        bool leftIsBST = isBST(root->left, min, root->val);
        bool rightIsBST = isBST(root->right, root->val, max);

        return isCurrent && leftIsBST && rightIsBST;
    }


    bool isValidBST(TreeNode* root) {

        return isBST(root, numeric_limits<int>::min(), numeric_limits<int>::max());

    }
    */

    // This type of solution works when root->left <= root->val <= root->right
    // This solution works too when root->left < root->val < root->right

    bool isBST(TreeNode* root, TreeNode* left = nullptr, TreeNode* right = nullptr) {

        if (!root)
            return true;

        if (left && left->val >= root->val)
            return false;

        if (right && right->val <= root->val)
            return false;

        return isBST(root->left, left, root) && isBST(root->right, root, right);
    }

    bool isValidBST(TreeNode* root) {

        return isBST(root);

    }

    /*
    vector<int> inOrderTraversal(TreeNode* root) {

        vector<int> answer;

        if (!root)
            return answer;

        vector<int> left = inOrderTraversal(root->left);
        answer.insert(answer.end(), left.begin(), left.end());
        answer.push_back(root->val);
        vector<int> right = inOrderTraversal(root->right);
        answer.insert(answer.end(), right.begin(), right.end());

        return answer;
    }

    // Do in-order traversal and check if the resulting array is sorted
    // This type of solution works when root->left <= root->val <= root->right
    // This solution works too when root->left < root->val < root->right
    bool isValidBST(TreeNode* root) {

        vector<int> answer = inOrderTraversal(root);

        for (int i = 1; i < answer.size(); ++i) {
            if (answer[i] <= answer[i-1])
                return false;
        }

        return true;
    }
    */


};