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 comment was a lifesaver for me.. I was really struggling to find a way to do this in linear time / constant space. I took your advice with the inorder traversal and used a single closure variable to store the last value visited instead of a list. I think that lead to a pretty concise solution. Thanks!

Can you explain how the single closure variable works? I tried to use a variable that I passed in to a helper function, but I'm assuming it was working they way I thought.

Actually that was a better approach. What he basically did was while comparing root->data with root->left data the last value will be set to root ->data and while the comparison is between root and its right child the last value will be the right child .Thus he made sure that a single comparison is enough for verifying the validity of the tree. A good one

I agree, the purely functional approach is probably better in hindsight for any real life application. The solution passing the var down would have avoided possible external side effects where mine uses a global variable.

I used the same approach, using the inorder traversal. But in my case I've used an instance of a class for storing the last value. Is it a good practise to do this?

I ended up with pretty much the same code but instead of a closure variable I just passed the variable in. I used a single element list since it's gets passed by reference which allows changes to persist when going back down the call stack:

thank you! I started with the same elegant code as yours but before I figured out that you can pass by reference with the list I had to change it to this bulky code:

Please note that your solution does not use constant memory but O(d) memory, where d is the depth of the tree. This memory is not allocated explicitly. It is allocated on the call stack with every recursive call. I do not know an algoritm which is linear in time and constant in memory, if anybody knows one I would be very interested :)

I know you have probably forgotten about this problem, but I had the same question and found an answer, so hopefully this helps somebody else who comes along:

The tree in question is:

----3

-2-----6

1-4---5-7

in a BST, all nodes and subnodes on the left must be less than the current node, and all nodes and subnodes to the right must be greater than the current node. The reson its not a BST is that 4 is to the left of 3

## Trees: Is This a Binary Search Tree?

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

can u post an explanation,cant make out your logic

Here is the Logic

The Inorder Traversal of the Binary Search Tree gives you the sorted array. i.e

if tree is something like this

Source :wiki

then its Inorder Traversal would be

A, B, C, D, E, F, G, H, I.

and now I have checked if the i th element is greater than its previous (i-1)th element

if the loop is over then return true else there is a violation and the tree isnt BST so return false

This comment was a lifesaver for me.. I was really struggling to find a way to do this in linear time / constant space. I took your advice with the inorder traversal and used a single closure variable to store the last value visited instead of a list. I think that lead to a pretty concise solution. Thanks!

Can you explain how the single closure variable works? I tried to use a variable that I passed in to a helper function, but I'm assuming it was working they way I thought.

Actually that was a better approach. What he basically did was while comparing root->data with root->left data the last value will be set to root ->data and while the comparison is between root and its right child the last value will be the right child .Thus he made sure that a single comparison is enough for verifying the validity of the tree. A good one

I agree, the purely functional approach is probably better in hindsight for any real life application. The solution passing the var down would have avoided possible external side effects where mine uses a global variable.

I used the same approach, using the inorder traversal. But in my case I've used an instance of a class for storing the last value. Is it a good practise to do this?

I ended up with pretty much the same code but instead of a closure variable I just passed the variable in. I used a single element list since it's gets passed by reference which allows changes to persist when going back down the call stack:

thank you! I started with the same elegant code as yours but before I figured out that you can pass by reference with the list I had to change it to this bulky code:

Please note that your solution does not use constant memory but O(d) memory, where d is the depth of the tree. This memory is not allocated explicitly. It is allocated on the call stack with every recursive call. I do not know an algoritm which is linear in time and constant in memory, if anybody knows one I would be very interested :)

I like the approach with inorder traverse. But we have to check not only the order, but also that there are no duplicates. I used "set" for that:

Here is my code:

Loved how you turned the list into a set to filter duplicates.

I first tried to check every node, but I couldn't figure out how to check the entire tree until I read your code, here's the code I tried first:

It doesn't work because it doesn't check for duplicates or if leafs are actually in order. Thanks for the elegant solution!

My code is:

Input:Output:Can anyone please where is the problem?

I know you have probably forgotten about this problem, but I had the same question and found an answer, so hopefully this helps somebody else who comes along:

The tree in question is:

----3

-2-----6

1-4---5-7

in a BST, all nodes and subnodes on the left must be less than the current node, and all nodes and subnodes to the right must be greater than the current node. The reson its not a BST is that 4 is to the left of 3

Thx I was missing this!