LeetCode 98. Validate Binary Search Tree

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)