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 &lt;= min:
        return False
    if root.value &gt;= 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 &lt;= min:
        return False
    if max is not None and root.value &gt;= 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 -&gt; (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 &lt; j for i,j in pairwise(traverse_in_order(root)))


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