## DEV Community is a community of 891,187 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Kaitian Xie

Posted on • Updated on

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