# Validate Binary Search Tree Solution

Validate Binary Search Tree is asked a lot in interview questions now a day. So, Today we will be discussing the algorithm and solution in Python, C++, and JAVA for this question.

## Question: Validate Binary Search Tree

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

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 = [1,2,3]
Output: true
```

Constraints:

• The number of nodes in the tree is in the range `[1, 104]`.
• `-231 <= Node.val <= 231 - 1`

## Solution in C++

As you can find this question on LeetCode. To know the solution below is the algorithm used to solve this problem.

### Algorithm:

It is really simple to validate the BST if you are aware of Inorder Traversal in BST. As per theory if you perform Inorder traversal on BST then you will receive the tree node values in ascending order. So we will follow the below steps.

• Perform Inorder Traversal on existing Tree.
• Store them in a List
• Now iterate through the list and compare each element is smaller than its descending elements.
```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void getInorder(TreeNode* root, vector<int> &getElem){
if(root==NULL) return;
getInorder(root->left,getElem);
getElem.push_back(root->val);
getInorder(root->right,getElem);
}
bool isValidBST(TreeNode* root) {
if(root==NULL) return true;
vector<int> getElem;
getInorder(root,getElem);
for(int i=0;i<getElem.size()-1;i++){
if(getElem[i]>=getElem[i+1]) return false;
}
return true;
}
};```

## Solution in Python

```class Solution:
def isValidBST(self, root: TreeNode) -> bool:
getList, prev = [], -math.inf
while getList or root:
while root:
getList.append(root)
root = root.left
root = getList.pop()
# If next element in inorder traversal
# is smaller than the previous one
# that's not BST.
if root.val <= prev:
return False
prev = root.val
root = root.right
return True```

## Solution in JAVA

```public class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
if (root == null) return true;
if (root.val >= maxVal || root.val <= minVal) return false;
return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
}
}```

Complexity Analysis

• Time complexity: O(N) in the worst case when the tree is BST or the “bad” element is a rightmost leaf.
• Space complexity: O(N) to keep stack.