We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

This is a really late reply but it may be of use to someone else.
float(-inf) and float(+inf) are basically starting numbers that have the property that no other number will be smaller or bigger than them.

So if n > float(-inf) and n < float(+inf) will always be true.

believe I had the same problem as you (our codes look similiar). So I reread the constraints of the problem and this bold part is important 'The data value of every node in a node's left subtree is less than the data value of that node.'

Hi, I know it's been three months since your comment, but I faced the same problem as you just now.

The problem with your (our) approach is that it only checks the upper or lower bound for each side, respectively.

Basically, there needs to be both an upper AND lower bound for each branch/node check. Some of the other submissions do this very well. This way all branches/nodes to the left are lower than the one above it, and all of the branches/nodes to the right are greater than the one above it.

A variation where a stack is used instead of recursion. I do not fancy recursion in Python as the maximum recursion depth is about 1000 per default. With the stack (a deque could also be used), you avoid a potential recursion limit error.

With the stack, no helper method is needed either.

I'm really bad at this kind of stuff but I'm actually going to throw caution to the wind and say no because you're appending to the input at the same time as looping through it. On the first itteration of the while loop you append two new items which on the next itteration will need to be pop-ed off and then possibly add another two calls.

Please correct me if I'm wrong, I'd be interested to hear from a computer scientist on this one.

i simplified it even further, incorporate the min and max instead of using another helper function, but use the default values :).
def checkBST(root, min=float('-inf'), max=float('inf')):
if not root:
return True
if root.data <=min or root.data >=max:
return False
return checkBST(root.left, min, root.data) and checkBST(root.right, root.data, max)

## Trees: Is This a Binary Search Tree?

You are viewing a single comment's thread. Return to all comments →

Thanks. Python 3 version:

Python 3 newbie here. Can you please explain float('-inf') and float('inf')?

This is a really late reply but it may be of use to someone else. float(-inf) and float(+inf) are basically starting numbers that have the property that no other number will be smaller or bigger than them.

So if n > float(-inf) and n < float(+inf) will always be true.

Can you explain what is float('-inf')

negative infinity and positive infinity

Hi, I can't see why my solution is wrong, it looks pretty similar. If anyone has an idea...

believe I had the same problem as you (our codes look similiar). So I reread the constraints of the problem and this bold part is important 'The data value of

everynode in a node's left subtree is less than the data value of that node.'Hi, I know it's been three months since your comment, but I faced the same problem as you just now.

The problem with your (our) approach is that it only checks the upper or lower bound for each side, respectively.

Basically, there needs to be both an upper AND lower bound for each branch/node check. Some of the other submissions do this very well. This way all branches/nodes to the left are lower than the one above it, and all of the branches/nodes to the right are greater than the one above it.

A variation where a stack is used instead of recursion. I do not fancy recursion in Python as the maximum recursion depth is about 1000 per default. With the stack (a deque could also be used), you avoid a potential recursion limit error.

With the stack, no helper method is needed either.

Wow, I was impressed with a few other submissions, but this, this is really good. +1

Impressive! Am I right to say that this is an O(n) solution?

I'm really bad at this kind of stuff but I'm actually going to throw caution to the wind and say

nobecause you're appending to the input at the same time as looping through it. On the first itteration of the while loop you append two new items which on the next itteration will need to be pop-ed off and then possibly add another two calls.Please correct me if I'm wrong, I'd be interested to hear from a computer scientist on this one.

This dynamic programming allows to skip reqursion, which is high performance gain.

I took your solution and enhanced it with one overloaded function:

def checkBST(root , min=float('-inf'), max=float('+inf')): if root == None: return True if root.data <= min or root.data >= max: return False return checkBST(root.left, min, root.data) and checkBST(root.right, root.data, max)

i simplified it even further, incorporate the min and max instead of using another helper function, but use the default values :). def checkBST(root, min=float('-inf'), max=float('inf')): if not root: return True if root.data <=min or root.data >=max: return False return checkBST(root.left, min, root.data) and checkBST(root.right, root.data, max)