# LeetCode: 98. Validate Binary Search Tree

**The Problem**

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
the node's key.**less than** - The right subtree of a node contains only nodes with keys
the node's key.**greater than** - Both the left and right subtrees must also be binary search trees.

**Example**

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

**Constraints:**

- The number of nodes in the tree is in the range
`[1, 10`

.^{4}] `-2`

^{31}<= Node.val <= 2^{31}- 1

**Solution**

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

```
bool isValidBST(TreeNode* root) {
vector<int> inorder;
trasverse(root, inorder);
for(int i = 1; i < inorder.size(); ++i)
if(inorder[i-1] >= inorder[i]) return false;
return true;
}
void trasverse(TreeNode* root, vector<int> &vec) {
if (root == NULL) return;
trasverse(root->left, vec);
vec.push_back(root->val);
trasverse(root->right, vec);
}
```

Here's a breakdown of how the code works:

1. `bool isValidBST(TreeNode* root)`

: This is the main function that checks if the binary tree rooted at `root`

is a valid BST. It returns `true`

if it is a valid BST and `false`

otherwise.

2. `vector<int> inorder;`

: A vector named `inorder`

is created to store the in-order traversal of the binary tree. In an in-order traversal, you visit the left subtree, then the current node, and then the right subtree, resulting in a sorted list of values for a valid BST.

3. `trasverse(root, inorder);`

: This line calls the `trasverse`

function to perform an in-order traversal of the binary tree `root`

and populates the `inorder`

vector with the values of the nodes in sorted order.

4. The `for`

loop iterates through the `inorder`

vector from index 1 to the end.

`if (inorder[i-1] >= inorder[i]) return false;`

: Inside the loop, it checks if the previous value (`inorder[i-1]`

) is greater than or equal to the current value (`inorder[i]`

). If this condition is met, it means that the tree is not a valid BST because a valid BST should have values in ascending order. If this condition is true for any pair of adjacent values, the function immediately returns`false`

.

5. If the loop completes without finding any adjacent values violating the BST property, it means the binary tree is a valid BST, and the function returns `true`

.

6. `void trasverse(TreeNode* root, vector<int> &vec)`

: This is a recursive helper function that performs the in-order traversal of the binary tree. It starts at the root node and recursively traverses the left subtree, then appends the value of the current node to the `vec`

vector, and finally recursively traverses the right subtree. This ensures that the values are added to the vector in ascending order.