Function to determine whether tree is a valid BST?

Question

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!

If `.. or root.left).val < root.val` is false, should you not immediately return `False`? (And the same - inverted - for `right`.) — Jongware, Jan 05 '17 at 17:43
Use `is None` when comparing with `None` http://stackoverflow.com/questions/3257919/what-is-the-difference-between-is-none-and-none — Jacob Krall, Jan 05 '17 at 17:45
And all those parentheses in your `if` statements are unnecessary. — Jacob Krall, Jan 05 '17 at 17:45
... why all those useless parenthesis? `(root.left).val`?!? Ugh! — Bakuriu, Jan 05 '17 at 17:48
@JacobKrall: my Python-fu is not yet strong enough to cough up a ready solution. As you also have suggested a few further improvements, please go ahead. — Jongware, Jan 05 '17 at 17:49
@TavianBarnes the list is the input (so that would be passed in as root) — Jane Sully, Jan 05 '17 at 17:54
I think you have to implement `min()` and `max()`. Consider a tree: `root.val=2`, `root.left.val=1`, `root.left.right.val=3`, with all other nodes set to `None`. That invalid BST would pass your algorithm, wouldn't it? — Robᵩ, Jan 05 '17 at 18:04
@Robᵩ Thanks for pointing that out. I was just playing around with testcases and I realized that very issue. Do you mind posting a solution? The min/max approach is confusing for me so I would love to see either code or pseudocode with comments. — Jane Sully, Jan 05 '17 at 18:09
@Robᵩ: i love how you caught that, and the 3 answerers (including me) so far didn't :) — Jacob Krall, Jan 05 '17 at 18:11
@JaneSully - my first attempt at using max() and min() would be exponentially slow, and I need to get back to my real job. I think the thing to do is to compute validity in a depth-first visit, and compute max and min values in the same visit, bubbling up as we go. — Robᵩ, Jan 05 '17 at 18:24
Your current approach is fundamentally wrong in at least one major way - if `root.left` is `None` or `root.left.val < root.val`, then you will never even look at the right sub-tree... — twalberg, Jan 05 '17 at 18:29

score 3 · Answer 1 · answered Jan 05 '17 at 18:26

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

Thank you so much! I really appreciate this! – Jane Sully Jan 07 '17 at 18:23 — Jane Sully, Jan 07 '17 at 18:23

Robᵩ · Answer 2 · 2017-01-05T19:33:13.077

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

Function to determine whether tree is a valid BST?

2 Answers2