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
– sharpshine99, Commented Oct 31, 2021 at 23:12

Daniel Hao · Accepted Answer · 2021-11-01 17:10:06Z

4

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!

edited Nov 1, 2021 at 17:10

answered Nov 1, 2021 at 10:36

Daniel Hao

4,9793 gold badges13 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

slago Over a year ago

I think it would be better to write "+inf", to highlight the difference.

Daniel Hao Over a year ago

Notes taken. Thanks.

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

0

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

answered Nov 1, 2021 at 0:00

Alain T.

42.2k4 gold badges36 silver badges57 bronze badges

Collectives™ on Stack Overflow

Validate a binary search tree using recursion

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related