> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/binary-search-tree/is-this-a-binary-search-tree.md).

# 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:**

![](https://assets.leetcode.com/uploads/2020/12/01/tree1.jpg)

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

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/12/01/tree2.jpg)

```
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

```cpp
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;
}
```

```cpp
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

```cpp
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.