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)
Top comments (0)