### 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; In.addAll(inOrder(root.left)); In.add(root.val); In.addAll(inOrder(root.right)); 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**

- How to Invert Binary Tree
- Find Minimum Depth of Binary Tree
- Find Number of Islands
- Maximum Depth of N-ary Tree
- Count Unique Binary Search Trees

## Comments

## Post a Comment