# LeetCode – Validate Binary Search Tree (Java)

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.

Java Solution 1 - Recursive

All values on the left sub tree must be less than parent and parent's parent, and all values on the right sub tree must be greater than parent and parent's parent. So we just check the boundaries for each node.

```public boolean isValidBST(TreeNode root) { return isValidBST(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY); }   public boolean isValidBST(TreeNode p, double min, double max){ if(p==null) return true;   if(p.val <= min || p.val >= max) return false;   return isValidBST(p.left, min, p.val) && isValidBST(p.right, p.val, max); }```

This solution also goes to the left subtree first. If the violation occurs close to the root but on the right subtree, the method still cost time O(n) and space O(h).

The following solution can handle violations close to root node faster.

```public boolean isValidBST(TreeNode root) { return helper(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY); }   public boolean helper(TreeNode root, double min, double max){ if(root==null){ return true; }   if(root.val<=min||root.val>=max){ return false; }   boolean isLeftBST = helper(root.left, min, root.val); boolean isRightBST = helper(root.right, root.val, max);   if(!isLeftBST||!isRightBST){ return false; }   return true; }```

Java Solution 2 - Iterative

```public class Solution { public boolean isValidBST(TreeNode root) { if(root == null) return true;   LinkedList<BNode> queue = new LinkedList<BNode>(); queue.add(new BNode(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY)); while(!queue.isEmpty()){ BNode b = queue.poll(); if(b.n.val <= b.left || b.n.val >=b.right){ return false; } if(b.n.left!=null){ queue.offer(new BNode(b.n.left, b.left, b.n.val)); } if(b.n.right!=null){ queue.offer(new BNode(b.n.right, b.n.val, b.right)); } } return true; } } //define a BNode class with TreeNode and it's boundaries class BNode{ TreeNode n; double left; double right; public BNode(TreeNode n, double left, double right){ this.n = n; this.left = left; this.right = right; } }```

Time and space are both O(n).

Java Solution 3 - In-order traversal

Since inorder traversal of BST is ascending, so we can check the sequence. Time is O(n) and space is O(h). h is the height of the stack which is the tree's height.

Category >> Algorithms
If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For example:
```<pre><code>
String foo = "bar";
</code></pre>
```
• akash kumar

private static boolean isBST(Node root, int minValue, int maxValue) {

if(root==null)
return true;
if(root.data=maxValue)
return false;
return isBST(root.left, minValue, root.data)
&& isBST(root.right, root.data, maxValue);
}

• randheer reddy

class Solution {
public boolean isValidBST(TreeNode root) {
return isBST(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY);
}
public boolean isBST(TreeNode tree, double min, double max) {
if (tree == null) {
return true;
}
if(tree.val=max){
return false;
}
return isBST(tree.left, min, tree.val) && isBST(tree.right, tree.val,max);
}

}

• randheer reddy

if a value less than a parent it should be less than its parents parent. Above code will still validate that since it is recursive. Please give me an example for your UC.

• ryanlr

The left child value needs to be not only smaller than parent, also smaller than parent’s parent value.

• randheer reddy

public boolean isBST(BSTNode tree) {
if (tree == null) {
return true;
}
if (tree.left != null && tree.left.val > tree.val) {
return false;
}
if (tree.right != null && tree.right.val < tree.val) {
return false;
}
return isBST(tree.left) && isBST(tree.right);
}

• Birendra Singh

here initial call would be validateBST(root,true)

• Birendra Singh

My Recursive solution-
static boolean validateBST(TreeNode root, boolean isValid)
{

if (isValid && root != null) {
if ((root.leftNode != null && root.value root.rightNode.value)) {
isValid = false;
} else
{
isValid = true;
}
if (isValid ) {
isValid =validateBST(root.leftNode,isValid);
//}
//if (isValid && root.value >= root.rightNode.value) {
isValid =validateBST(root.rightNode,isValid);
}
}
return isValid;
}

• Stefanus Anggara

where the difference between queue.add and queue.offer?
what if I always use queue.add to insert new object to LinkedList?

• Venk

Nice One

• Udaydeep Thota

If I want to validate the BST allowing duplicates in the tree (say right node can contain elements greater than or EQUAL to root, how could any of the recursive solution be modified ?

• Matias SM

A recursive implementation for any type (not restricted to numbers):

``` boolean isBst(BinTreeNode root, Comparator cmp) { return isBst(root, Optional.empty(), Optional.empty(), cmp); }```

``` ```

``` boolean isBst(BinTreeNode root, Optional minValue, Optional maxValue, Comparator cmp) { if (root == null) return true; if (minValue.map(min -> cmp.compare(root.value, min) > 0).orElse(Boolean.TRUE) && maxValue.map(max -> cmp.compare(root.value, max) < 0).orElse(Boolean.TRUE)) { return isBst(root.left, minValue, Optional.of(root.value), cmp) && isBst(root.right, Optional.of(root.value), maxValue, cmp); } return false; } ```

• Matias SM

Note to avoid bad generalizations. A BST _can_ have duplicated values (if required). However, according to this exercise, it can’t (strict order is required as defined by the rules).

“…Whether duplicates, i.e. different elements with same key, shall be allowed in the tree or not, does not depend on the order relation, but on the application only…”
https://en.wikipedia.org/wiki/Binary_search_tree

• Rush

if(root.val=high) return false;

‘=’ in condition confirms that no node value appear more than once.

• Rush

BST can’t have duplicate values. Hence, while checking we include equal condition.

• BruceLee

it will not work for

10

/

5 12

/

4 11

which is NOT a valid BST, but your solution may return true,

• Gaurav Khurana

I think it could be simply

public bool ValidateBST(Node node)
{
if (node == null)
{
return true;
}

if ((node.Left != null && node.Left.Value > node.Value) || (node.Right != null && node.Right.Value < node.Value))
{
return false;
}

return (ValidateBST(node.Left) && ValidateBST(node.Right));
}

For iterative solution how about inorder tree traversal and compere its previous value with current node? Following code is in C#.
``` public bool IsBST(TreeNode root) { Stack s = new Stack(); TreeNode p = root; int? nVal = null; // previous value```

``` ```

``` while (s.Count != 0 || p != null) { if (p != null) { s.Push(p); p = p.left; } else { TreeNode node = s.Pop(); p = node.right; if (nVal != null && nVal > node.val) return false; nVal = node.val; } } return true; } ```

• if i was right,
it should be “if(p.val = max) return false;”

Property of the BST: all left descendents <= n < right descendents, for each node n

• Shaurya Kalsi

why isn’t it if(p.val max). Why do we also exclude it when it is equal?

• ryanlr

problem is fixed.

• DonBear

You are right.

• DonBear

You are right.

• I think the algorithm will fail if the tree is a single node with the root value set to Integer.MIN_VALUE or Integer.MAX_VALUE. I think we should define min and max to double or long to be safe.

• Laura

Does this fail because it never checks that the keys are unique? Requirement for BST is that the keys are unique.

• XiY

solution is right
Through validate(root.left, min, root.val), in the “5” level, max is root.val which is 10 in your example, when you move deeper to the next recursion, the value of max in validate(root.right, root.val, max) is exact root.val which = 10, that is out of the range and return false.

• jhorwit

nvm

• jhorwit

This solution will not work. Imagine a tree:

10
/
5 12
/
4 11

The method above will return true since 11 is greater than 5; however, 11 is greater than 10 so it should be in the right subtree from root.

• Cong

Hey, I think you should evaluate the keys of the root, its left and right children first, before you go down to the recursion. The current version will always return true.
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}