### Validate Binary Search Tree - The Coding Shala

Last Updated: 27-Jan-2021
Home >> Interview Questions >> Validate Binary Search Tree

In this post, we will learn how to Validate Binary Search Tree and will implement its solution in Java.

## Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a 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:
2
/ \
1   3

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

Example 2:
5
/ \
1   4
/ \
3   6

Input: [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.

## Validate Binary Search Tree Java Program

Approach 1

Using recursion and inorder traversal. We can get the list of nodes in In-Order and InOrder is always in ascending order of value.

Java Program:

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inOrder(TreeNode root){
List<Integer> In = new ArrayList<Integer>();
if(root == null) return In;
return In;
}

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

Approach 2

Iterative Solution.[Using Stack/dfs]

Java Program:

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
if(root == null) return true;
Stack<TreeNode> st = new Stack<TreeNode>();
TreeNode check = null;
while(root != null || !st.empty()){
while(root != null){
st.push(root);
root = root.left;
}
root = st.pop();
if(check != null && root.val <= check.val) return false;
check = root;
root = root.right;
}
return true;
}
}
```

Other Posts You May Like