Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Example

An example:

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

class Solution {
public:
    
   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;
   }
  
   bool isValidBST(TreeNode *root) {
        TreeNode *prev = NULL;
        return isValidBST(root, prev);
   }
};

 
class Solution {
public:
   bool isValidBST(TreeNode *root, long long mn, long long mx)
   {
       if (!root) return true;
       if (root->val <= mn) return false;
       if (root->val >= mx) return false;
       
       return isValidBST(root->left, mn, root->val) &&isValidBST(root->right, root->val, mx);
       
   }
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    bool isValidBST(TreeNode *root) {
        return isValidBST(root, (long long)INT_MIN-1, (long long)INT_MAX+1);
    }
};

 
class Solution {
public:
    bool isValidBST(TreeNode *root) {
        stack<TreeNode *> st;
        pushLeft(root, st); 
        
        TreeNode *prev = NULL;
        while(st.size() > 0)
        {
            root = st.top();
            st.pop();
            if (prev && prev->val >= root->val) return false;
            prev = root;
            pushLeft(root->right, st);
        }
        
        return true;
    }
    void pushLeft(TreeNode *root, stack<TreeNode *> &st)
    {
        while(root)
        {
            st.push(root);
            root = root->left;
        }
    }
};

class Solution {
public:
    bool isValidBST(TreeNode *root) {
        stack<TreeNode *> st;
        
        TreeNode *prev = NULL;
        while(!st.empty() || root)
        {
            if (!root)
            {
                root =  st.top();
                st.pop();
                
                if (prev && prev->val >= root->val) return false;
                prev = root;
                root = root->right;
            }
            else {
                st.push(root);
               root = root->left;
            }
        }
        return true;
    }
};