# LeetCode 98. Validate Binary Search Tree Kaitian Xie Updated on ・2 min read

# Recursion

public class Solution {
public boolean isValidBST(TreeNode root) {
return isValid(root, null, null);
}

private boolean isValid(TreeNode p, Integer low, Integer high) {
if (p == null) {
return true;
}

return (low == null || p.val > low) && (high == null || p.val < high) && isValid(p.left, low, p.val) && isValid(p.right, p.val, high);
}
}


In a BST, a left child node is smaller than its parent and a right child node is always greater than its parent. The solution is based on this property. In the isValid function, we recursively check if a node has a value between low and high. There is an edge case where a node may have a value equal to Integer.MIN_VALUE or Integer.MAX_VALUE. So we use null to represent the infinity.

Time Complexity: O(n)

Extra Space: O(1)

# In-Order Traversal

public class Solution {
private TreeNode prev;

public boolean isValidBST(TreeNode root) {
prev = null;
return isMonotonicIncreasing(root);
}

private boolean isMonotonicIncreasing(TreeNode p) {
if (p == null) {
return true;
}

if (isMonotonicIncreasing(p.left)) {
if (prev != null && p.val <= prev.val) {
return false;
}
prev = p;
return isMonotonicIncreasing(p.right);
}

return false;
}
}


If the tree is a valid BST, its elements should strictly follow an increasing order within an in-order traversal. We can use this property to solve the problem. To learn more about in-order traversal, please check out this link. We define prev to keep a track of the previous element in the in-order traversal. Whenever we detect that there exists a TreeNode p that is smaller than prev, we know the tree is not a valid BST.

Time Complexity: O(n)

Extra Space: O(1)

### Discussion   