# 5 Java Accepted Solutions

• Solution 1: recursive, record the previous value, CONS: use global variable

``````class Solution {
Long prev = Long.MIN_VALUE;
boolean res = true;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return res;
}
helper(root);
return res;
}
private void helper(TreeNode root) {
if (root == null) {
return;
}
helper(root.left);
if (prev >= root.val) {
res = false;
return;
}
prev = (long) root.val;
helper(root.right);
}
}
``````

Solution 2: root.val has to be in the range of maximum in left subtree and minimum in right subtree, recursive

``````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);
}
}
``````

Solution 3: root.val has to be in the range, do not use global variable, worse than solution 2

``````class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
ResultType res = helper(root);
return res.isValid;
}
private ResultType helper(TreeNode root) {
if (root == null) {
return new ResultType(true, Long.MAX_VALUE, Long.MIN_VALUE);
}
if (root.left == null && root.right == null) {
return new ResultType(true, root.val, root.val);
}
ResultType left = helper(root.left);
ResultType right = helper(root.right);
if (left.isValid && right.isValid && left.max < root.val && root.val < right.min) {
return new ResultType(true, Math.min(root.val, left.min), Math.max(root.val, right.max));
} else {
return new ResultType(false, Math.min(root.val, Math.min(left.min, right.min)), Math.max(root.val, Math.max(left.max, right.max)));
}
}
}
class ResultType {
boolean isValid;
long min;
long max;
ResultType(boolean isValid, long min, long max) {
this.isValid = isValid;
this.min = min;
this.max = max;
}
}
``````

Solution 4: iterative inorder traversal, using stack

``````class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
long prev = Long.MIN_VALUE;
while (!stack.isEmpty() || cur != null) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if (cur.val <= prev) {
return false;
}
prev = cur.val;
cur = cur.right;
}
return true;
}
}
``````

Solution 5: iterative inorder traversal, Morris Traversal, space: O(1)

``````class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
TreeNode cur = root;
TreeNode pre = null;
long prev = Long.MIN_VALUE;
while (cur != null) {
if (cur.left == null) {
if (cur.val <= prev) {
return false;
}
prev = cur.val;
cur = cur.right;
} else {
pre = cur.left;
while (pre.right != null) {
pre = pre.right;
}
pre.right = cur;
TreeNode temp = cur;
cur = cur.left;
temp.left = null;
}
}
return true;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.