Home » leet code » Leet Code : Validate Binary Search Tree Java | CPP | Python solution

# Leet Code : Validate Binary Search Tree Java | CPP | Python solution

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

## Solution :

Java DFS :

``````class Solution {
public boolean isValidBST(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
doDFS(root, list);
int size = list.size();
for(int i=1; i<size; i++) {
if(list.get(i-1) >= list.get(i))
return false;
}
return true;
}

private void doDFS(TreeNode root, ArrayList<Integer> list) {
if(root!=null) {
doDFS(root.left, list);
doDFS(root.right,list);
}
return;
}
}``````

Python :

``````class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
res = self.inorder(root, [])
return True if res == sorted(res) and len(res) == len(set(res)) else False

def inorder(self, root, res):
if root:
self.inorder(root.left, res)
res.append(root.val)
self.inorder(root.right , res)
return res``````

CPP :

Inorder solution :

``````class Solution {
public:
vector<int> v;
void helper(TreeNode *root)
{
if(root == NULL)
return;

helper(root -> left);
v.push_back(root -> val);
helper(root -> right);

}
bool isValidBST(TreeNode* root) {

helper(root);
for(int i = 0 ; i < v.size() - 1; i++)
{
if(v[i] >= v[i + 1])
return false;
}
return true;
}
};``````