CODEWITHSUNDEEP
pythondata-structurestree
sharpshine99
sharpshine99

Reputation: 23

Validate a binary search tree using recursion

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"))

Upvotes: 2

Views: 1405

Answers (2)

Daniel Hao
Daniel Hao

Reputation: 4980

Actually, you are not too far off. You just missed one place - see the code:

Here it's the same idea, but code little differently to match your orig. logic and compare with your Post.

[Note] Inspired by Alain and OP recursion idea. So credit to them. ;-)

 def isValidBST(self, root: TreeNode) -> bool:
     
     def validate(node, lower, upper):
         if not node:  return True    # empty node/Tree considered BST

         # compare the node range is still valid: between low and high
         if node.val > lower and node.val < upper:
            return validate(node.left, lower, node.val) and \
                   validate(node.right, node.val, upper)
            return False
     return validate(root, float("-inf"), float("+inf")) # <--- miss here!

Upvotes: 4

Alain T.
Alain T.

Reputation: 42143

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

Upvotes: 0

Related Questions