# LeetCode 98. Validate Binary Search Tree

### Kaitian Xie γ»2 min read

LeetCode in Java (8 Part Series)

# 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)`

LeetCode in Java (8 Part Series)