Im attempting to write an algorithm that validates a binary search tree. This is to answer the following algorithm question:

This is clearly not a valid binary search tree, since the node 3 is less than it's grand parent 5.

In a binary search tree, every node to the right (including all ancestors), must be greater (or grater or equal depending on your definition). The same goes for the left sub trees. Please note that the leetcode problem in this case specifically states that they must be less and greater so equal is not valid. Think about it this way: You need to be able to do a binary search in a BST. When you go right, you expect all the nodes there to be greater than the parent. If a node less than the parent is found there, the ordering is broken and you can't do a binary search. You need to search linearly. Binary searching for 3 in this example would return false, while it's clearly there. So, it isn't a valid binary search tree.

Your algorithm only checks whether the immediate left and right children respect this condition.

To correct it, you need to pass down the min and max allowed values to the recursive function. When you go left, you set the max value equal to the current node value. When you go right you set the min value to the current node value. This makes sure that, say the nodes to the left of a node are never greater than that node.

A possible implementation is as follows:

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        return self.isValidBSTHelper(root, None, None)
    def isValidBSTHelper(self, root: TreeNode, min_val: int, max_val: int)-> bool:
        if root == None: return True
        if (min_val != None and root.val <= min_val) or (max_val != None and root.val >= max_val):
            return False
        
        return self.isValidBSTHelper(root.left, min_val, root.val) \
                and self.isValidBSTHelper(root.right, root.val, max_val)