Module 15 - failing 2 performance tests

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.

You have a mistake in your logic . Try visualising the following example :

        / \
       3   7
      / \ 
     1   6

The following tree will satisfy your given conditions but it isn’t a BST. I hope you will improve your logic and find the correct algorithm for this question.

1 Like

Closing this topic as your issue is resolved by the mentor. If it is still not resolved, Kindly un-mark the accepted solution or create a new topic and post this question as a reference link in the description of the new topic.