1.Is This a Binary Search Tree

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

A valid 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 1:

Input: root = [2,1,3]
Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

A binary search tree (BST) has the following properties. • The left subtree of a node contains only nodes with keys less than the root node’s key. • The right subtree of a node contains only nodes with keys greater than the root node’s key. • Both the left and right subtrees must also be binary search trees.

From the above properties it naturally follows that: • Each node (item in the tree) has a distinct key.

Using Inorder Traversal

vector<int> v;
void inOrder(Node *t)
{
    if (t == NULL)
    {
        return;
    }
    inOrder(t->left);
    v.push_back(t->data);
    inOrder(t->right);
}

bool checkBST(Node *root)
{

    inOrder(root);
    bool res = true;
    for (int i = 0; i < v.size() - 1; i++)
    {
        if (v[i + 1] <= v[i])
        {
            res = false;
            break;
        }
    }
    return res;
}

class Solution
{
public:
    bool isValidBST(TreeNode *root)
    {
        if(root == NULL){return true;}
        if(root->left==NULL && root->right==NULL){return true;}
        
        stack<TreeNode *> s;
        TreeNode *t = root;
        int prev = INT_MIN;
        bool res = true;
        vector<int> v;
        while (t != NULL || !s.empty())
        {

            if (t != NULL)
            {
                s.push(t);
                t = t->left;
            }
            else
            {
                t = s.top();
                v.push_back(t->val);
                s.pop();
                t = t->right;
            }
        }
        
        for(int i=0;i<v.size()-1;i++){
            if(v[i+1]<=v[i]){
                res = false;
                break;
            }
        }

        return res;
    }
};

Time Complexity O(n) and Space Complexity O(n). This solution uses an extra space complexity of O(n)

Solution II

class Solution
{
public:
    bool isValidBST(TreeNode *root)
    {

        stack<TreeNode *> s;
        TreeNode *t = root;
        int prev = INT_MIN;
        bool res = true;
        while (t != NULL || !s.empty())
        {

            if (t != NULL)
            {
                s.push(t);
                t = t->left;
            }
            else
            {
                t = s.top();
                if (t->val > prev)
                {
                    prev = t->val;
                }
                else
                {
                    res = false;
                    break;
                }
                s.pop();
                t = t->right;
            }
        }

        return res;
    }
};

In this solution, if we check while doing inorder traversal we have an edge case if the tree has INT_MIN as one of its nodes it can create the error.