I am using the following approach:
If the tree is empty, return true
If the left subtree is empty or the root of the left subtree has a lesser value than the root value, and
if the right subtree is empty or the root of the right subtree has a greater value than the root value, then recurse for both left and right subtrees and return whether or not both of them are valid BSTs.
Else, return false.
This approach is failing 2 tests - perf-test-4 and perf-test-7. I cannot think of any other optimization that can be made; please help me out.