Leetcode -- Validate Binary Search Tree

 /**  
  * 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) {  
     if(root == NULL) {  
       return true;  
     }  
     if(root->left != NULL) {  
       bool isLeft = isValidBST(root->left);  
       if(!(isLeft && rightMost(root->left) < root->val )) {  
         return false;  
       }   
     }  
     if(root->right != NULL) {  
       bool isRight = isValidBST(root->right);  
       if(!(isRight && leftMost(root->right) > root->val)) {  
         return false;  
       }  
     }  
     return true;  
   }  
   int leftMost(TreeNode *root) {  
     if(root == NULL) {  
       return INT_MIN;  
     }  
     while(root->left != NULL) {  
       root = root->left;  
     }  
     return root->val;  
   }  
    int rightMost(TreeNode *root) {  
     if(root == NULL) {  
       return INT_MAX;  
     }  
     while(root->right != NULL) {  
       root = root->right;  
     }  
     return root->val;  
   }  
 };  

Another Method, even better

 /**  
  * 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 isValidBSTHelper(root, INT_MIN, INT_MAX);  
   }  
   bool isValidBSTHelper(TreeNode * root, int min, int max) {  
     if(root == NULL) {  
       return true;  
     }  
     if(root->val <= min || root->val >= max) {  
       return false;  
     }  
     if(!isValidBSTHelper(root->left, min, root->val)) {  
       return false;  
     }  
     if(!isValidBSTHelper(root->right, root->val, max)) {  
       return false;  
     }  
     return true;  
   }  
 };  

Recursion method

 /**  
  * 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) {  
     TreeNode * prev = NULL;  
     return isValidBST(root, prev);  
   }  
   bool isValidBST(TreeNode * root, TreeNode *& prev) {  
     if(!root) {  
       return true;  
     }  
     if(!isValidBST(root->left, prev)) {  
       return false;  
     }  
     if(prev && prev->val >= root->val) {  
       return false;  
     }  
     prev = root;  
     if(!isValidBST(root->right, prev)) {  
       return false;  
     }  
     return true;  
   }  
 };