https://leetcode.com/problems/validate-binary-search-tree

We need to check that some property holds for every node of our tree, so as usual any recursion method should work here. Let us use function dfs(node, low, high), where:

  1. node is node we are currently in
  2. low and high are bounds we expect to value of this node be in.

Now, let us go to the main algorithm:

  1. If we have None node, we are happy: empty tree is BST
  2. Next we check if low < node.val < high and if it is not true, we can immedietly return False.
  3. Finally, we check conditions for left children: its value should be in (low, node.val) and for right children: (node.val, high). If one of this dfs return False, we need to return False.

Complexity: time complexity is O(n) to traverse every node of our tree. Space complexity is O(h), where h is height of our tree.

class Solution:
    def isValidBST(self, root):
        def dfs(node, low, high):
            if not node: return True
            if not low < node.val < high: return False
            return dfs(node.left, low, node.val) and dfs(node.right, node.val, high)
        
        return dfs(root, -float("inf"), float("inf"))

If you like the solution, you can upvote it on leetcode discussion section: Problem 0098