Validate a binary search tree using recursion

Question

I am trying to validate a binary search tree. Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees.

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

I am using a recursive solution but it fails to pass this test case:
Input: [2,1,3]
Expected Output: True
My output: False

Example of a Sample Input: [5,1,4,null,null,3,6]
Expected Output: False
My output: False

Can someone please identify my mistake? Below is my code:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        
        
        def valid(node, left, right):
            if not node:
                return True
            
            if not (node.val>left and node.val<right):
                return False
            
            return (valid(node.left, left, node.val) and valid(node.right, node.val, right))
                    
        return valid(root, float("-inf"), float("-inf"))

Please check. I have edited the question and added a few sample inputs and outputs — sharpshine99

Alain T. Alain T. · Accepted Answer · 2021-11-01T00:00:19

You can push down the validation by providing a range of values for the left and right node in the recursion. This way, each node only has to check itself against the requirements passed down by its parent node, then recurse for its own subnodes.

def isBST(node,minVal=None,maxVal=None):
    if node is None: return True
    if minVal is not None and self.val<minVal: return False 
    if maxVal is not None and self.val>maxVal: return False
    if not isBST(self.left,minVal,self.val):   return False
    if not isBST(self.right,self.val,maxVal):  return False
    return True

Validate a binary search tree using recursion

1 Answers