Validate BST: Root.Val as Min and Max Threshold

First Thoughts

Recursion and AND (&&) can be used to return boolean values for left and right subtree validation. Base case includes the case where the node itself is null (return true if null), and returns false if the node's left value is greater than its value or if the node's right value is less than its own value.

My Solution

class Solution {
    public boolean isValidBST(TreeNode root) {
        return doWork(root);
    }
    
    private boolean doWork(TreeNode root) {
        if (root==null) return true;
        if (root.left!=null && root.left.val >= root.val) return false;
        if (root.right!=null && root.right.val <= root.val) return false;
        return doWork(root.left) && doWork(root.right);
    }
}

Improved Solution

class Solution {
	public boolean isValidBST(TreeNode root) {
    	return doWork(root, null, null);
    }
    
    private boolean doWork(TreeNode root, Integer low, Integer high) {
    	if (root==null) return true;
        if (low!=null && root.val <= low) return false;
        if (high!=null && root.val >= high) return false;
        return doWork(root.left, low, root.val) 
        && doWork(root.right, root.val, high)
    }
}

Catch Point

• Integer to encompass wider range of integers (int limit on very big numbers)
• Passing current root value as either a lower threshold or high threshold
• Then, need not check for left right values null, and applies to all sublevels