CODEWITHSUNDEEP
pythonrecursionbinary-search-tree
Jane Sully
Jane Sully

Reputation: 3327

Function to determine whether tree is a valid BST?

I have to determine whether given a list representing a tree, whether the tree is a valid BST (this question is taken from leetcode). I have seen other posts on this but I was wondering if someone could help me with my approach, since it is clearly not right. For example, for the tree [1,2,3] where 1 is the root, 2 is the left child, and 3 is the right child, my code returns true. Hopefully it only requires small changes, but it might be that the entire function's approach is incorrect.

Here is my code:

def isValidBST(self, root):
    if (root == None):
        return True
    if (root.left == None or root.left.val < root.val):
        return self.isValidBST(root.left)
    if (root.right == None or root.right.val > root.val):
        return self.isValidBST(root.right)
    return False

Secondly, I have seen approaches with a helper function that takes in a min/max value, but that confuses me. If anyone would also like to explain why that approach is a good/better one, that would be greatly appreciated!

Upvotes: 2

Views: 1468

Answers (2)

Robᵩ
Robᵩ

Reputation: 168616

Here is one way to implement the validity check:

class BST:

    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def isValidBST(self):
        '''
        Simultaneously check for validity and set our own min and max values.
        '''
        self.min = self.max = self.value
        if self.left:
            if not self.left.isValidBST():
                return False
            if self.left.max >= self.value:
                return False
            self.min = self.left.min
        if self.right:
            if not self.right.isValidBST():
                return False
            if self.right.min < self.value:
                return False
            self.max = self.right.max
        return True

assert BST(2, BST(1), BST(3)).isValidBST()
case = BST(2, BST(1, None, BST(3)))
assert case.left.isValidBST()
assert not case.isValidBST()

Upvotes: 0

Patrick Haugh
Patrick Haugh

Reputation: 60944

I'd make a min_max method for Nodes that finds the min and max values of the tree rooted at that Node. Do sanity checking while finding those, and then isValidBST can just catch the exception

def max_min(self): 

    '''
    Returns maximum and minimum values of the keys of the tree rooted at self. 
    Throws an exception if the results are not correct for a BST
    '''

    l_max, l_min = self.left.max_min() if self.left else (self.val, self.val)
    if l_max > self.val:
        raise ValueError('Not a BST')
    r_max, r_min = self.right.max_min() if self.right else (self.val, self.val)
    if r_min < self.val:
        raise ValueError('Not a BST')
    return l_min, r_max

def isValidBST(self):
    try:
        if self.max_min():
            return True
    except ValueError:
            return False

Upvotes: 3

Related Questions