# 98-Validate Binary Search Tree
###### tags: `Medium`
* Question:
https://leetcode.com/problems/validate-binary-search-tree/

* Hint:
1. 與recover BST用到概念類似，進行左右子樹迭帶，並檢查左<根?->移動節點->根<右?
2. 利用最小和最大值來代表要比較的兩個節點，注意遞迴時，左右子樹參數代入誰，用到的變數比recover BST少
3. DFS

* Reference:
觀念:
https://ithelp.ithome.com.tw/articles/10213279
code:
https://ithelp.ithome.com.tw/articles/10278114?sc=hot

## Solution I

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return frule(root, NULL, NULL);
    }
private:
    bool frule(TreeNode* cur, TreeNode* mini, TreeNode* maxi) {
        if (!cur) return true;
        if ( mini )
            if ( cur->val <= mini->val )
                return false;
        if ( maxi )
            if ( cur->val >= maxi->val)
                return false;

        return frule(cur->left, mini, cur) && frule(cur->right, cur, maxi);
    }
    
};

## Solution using DFS

class Solution {
public:
    bool isvalid(TreeNode* root,long long minVal,long long maxVal){
                if(root==NULL)
                    return true;
        if(root->val>=maxVal|| root->val<=minVal)
            return false;
        return isvalid(root->left,minVal,root->val)&& isvalid(root->right,root->val,maxVal);
    }
    bool isValidBST(TreeNode* root) {
        return isvalid(root,LONG_MIN,LONG_MAX);
        
    }
};