Validate Binary Search Tree

inorder traverse

    bool isValidBST(TreeNode *root) {
        int pre=INT_MIN;
        stack<TreeNode*> stk;
        TreeNode*pointer=root;
        while(pointer||!stk.empty()){
            if(pointer){
                stk.push(pointer);
                pointer=pointer->left;
            }
            else{
                pointer=stk.top();stk.pop();
                if(pre>=pointer->val)
                    return false;
                pre=pointer->val;
                pointer=pointer->right;
            }
        }
        return true;
    }

 //method 2
class Solution {
public:
   int maxval(TreeNode *root) {
       while(root->right)
        root=root->right;
       return root->val;
   }
   int minval(TreeNode *root) {
       while(root->left)
        root=root->left;
       return root->val;
   }
    bool isValidBST(TreeNode *root) {
        if(!root)
            return true;
        if(root->left==NULL&&root->right==NULL)
            return true;
          
        if(root->right==NULL)
            return maxval(root->left)<root->val &&isValidBST(root->left);
        else if(root->left==NULL)
            return minval(root->right)>root->val&&isValidBST(root->right);
        else return maxval(root->left)<root->val &&isValidBST(root->left)&&minval(root->right)>root->val&&isValidBST(root->right);   
    }
};

//method 3 and 4, from anniekim
Solution: Recursion. 1. Add lower & upper bound. O(n)
  2. Inorder traversal with one additional parameter (value of predecessor). O(n)
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
    bool isValidBST(TreeNode *root) {
        return isValidBST_1(root);
    }
    // solution 1: lower bound + higher bound
    bool isValidBST_1(TreeNode *root) {
        return isValidBSTRe_1(root, INT_MIN, INT_MAX);
    }
    bool isValidBSTRe_1(TreeNode *node, int lower, int upper){
        if (!node) return true;
        if (node->val <= lower || node->val >= upper) return false;
        return isValidBSTRe_1(node->left, lower, node->val) &&
            isValidBSTRe_1(node->right, node->val, upper);
    }
    // solution 2: inorder
    bool isValidBST_2(TreeNode *root) {
        int val = INT_MIN;
        return isValidBSTRe_2(root, val);
    }
    bool isValidBSTRe_2(TreeNode *node, int &val)
    {
        if (!node) return true;
        if (node->left && !isValidBSTRe_2(node->left, val))
            return false;
        if (node->val <= val)
            return false;
        val = node->val;
        if (node->right && !isValidBSTRe_2(node->right, val))
            return false;
        return true;
    }
};