Python function to determine whether a given BST is valid

Here's a simple function I wrote using recursion. Does this run in \$O(n)\$ time and use \$O(n)\$ space, where \$n\$ is the number of nodes in the tree?

def is_valid(root, min, max):
    if not root:
        return True
    if min is None or max is None:
        return is_valid(root, float("-inf"), float("+inf"))
    print(root.value, min, max)
    if root.value = max:
        return False
    return is_valid(root.left, min, root.value) and is_valid(root.right, root.value, max)

Stick with None

One of the things you do is effectively convert Nones into -inf and +inf. But that's not necessary. Stick with None, and then you can ignore those comparisons. I would additionally explicitly default the arguments:

def is_valid(root, min=None, max=None):
    if not root:
        return True
    if min is not None and root.value = max:
        return False
    return is_valid(root.left, min, root.value) and is_valid(root.right, root.value, max)

I also removed the print - since you don't really want random output as you go through your function.

Besides that, looks good to me. The last line is a bit long, so I might wrap it in parentheses just so I can do:

return (is_valid(root.left, min, root.value) and 
            is_valid(root.right, root.value, max))

Try to keep your lines below 80 characters.

An alternate implementation, just throwing it out as an idea for thinking about the problem completely differently is this. A BST is valid if it's in-order traversal is actually ordered. An in-order traversal would be:

def traverse_in_order(root):
    if root:
        yield from traverse_in_order(root.left)
        yield root.value
        yield from traverse_in_order(root.right)

In Python2.7, replace yield from X with for x in X: yield x. Basically, we're turning our tree into an iterable. Then, we can just pairwise iterate over this with some itertools recipes:

def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return izip(a, b)

And just check that every pair is in strictly increasing order:

def is_valid(root):
    return all(i < j for i,j in pairwise(traverse_in_order(root)))

Not saying this is better than your original approach, but it's certainly different.

StackExchange Code Review Q#111202, answer score: 5