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.

Maybe we should explain a little further. The Wikipedia algorithm consists of simply doing a recursive binary tree search and then attaching a node when you hit null.

If somebody assumes the input is processed in order, they would be confused because the sample tree given on the problem page would be impossible to build, as would your example tree.

Your data is 1 2 3 4 5 6 7

The initial node is null, so the first node attached will have value 1, and 1 will be the root of your tree.

Based on your example, it looks like there's an assumption that the input is expected to be an ordered array, and thus that the root of any given (sub-)tree can be determined by simply taking the middle value. Something like this:

/* A function that constructs Balanced Binary Search Tree from a sorted array */NodesortedArrayToBST(intarr[],intstart,intend){/* Base Case */if(start>end){returnnull;}/* Get the middle element and make it root */intmid=(start+end)/2;Nodenode=newNode(arr[mid]);/* Recursively construct the left subtree and make it left child of root */node.left=sortedArrayToBST(arr,start,mid-1);/* Recursively construct the right subtree and make it right child of root */node.right=sortedArrayToBST(arr,mid+1,end);returnnode;}

The problem should state that the input is in the order that the in-order traversal of the tree would yield, if that is the case.

Actual test case:
2
1 2 4 3 5 6 7

Output:
No

Let's test the in-order assumption:
1: We take the middle of {1 2 4 3 5 6 7}, which is 3, and it's the first node inserted, so it becomes the root
2: We take the middle of {1 2 4}, which is 2
3: 2 is less than 3, so we attach it to the left
4: We take the middle of {5 6 7}, which is 6

3/ \
26

5: We take the middle of {1}, which is 1, and goes left of 2, and the middle of {4}, which is 4, and goes right of 2; we do the same for the right side of the array, and get:

3/ \
26/\/ \
1457

And we see the problem - the (4) node is in the left sub-tree of the (3) node, which violates the binary search tree definition. Thus we return false, the stub code prints "No," and we have confirmed the assumption of the input order.

I attempted to explain why his comments weren't constructive, but he wasn't listening. This is why I deleted my comments. I agree with you and said something similar, but he kept thinking I was insulted by his comments. It's unfortunate to see that another developer is being so judgemental and using insults instead of working together to make other developers better. Fortunately, the people that are open to teaching and providing constructive feedback are the ones that end up making the largest impact, and become the best developers. Hopefully he will think about his actions and decide to turn his attitude around.

Ah crap - I was scratching my head until I read your last point here. Then I went and read the problem again. Attention to detail is important! I fully missed "value of every node"

I am confused. I know what the order of insertion in a Binary Search Tree is but the problem said "given the root node of a binary tree", not "given a root node of a binary search tree", so we can't assume the input will be inserted by the order of insertion in a BST. Besides, the objective of the problem is to verify if the Binary Tree given is a BST or not. If the binary tree is constructed with a BST's order of insertion, then the output will always be 'Yes'

## Trees: Is This a Binary Search Tree?

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

How do I know the insertion order? I mean since I have 1 2 3 4 5 6 7 I'm assuming that the middle value is the root but what after?

Check from the web regarding to this topic. for example: https://en.wikipedia.org/wiki/Binary_search_tree. it will help you understanding it.

Maybe we should explain a little further. The Wikipedia algorithm consists of simply doing a recursive binary tree search and then attaching a node when you hit null.

If somebody assumes the input is processed in order, they would be confused because the sample tree given on the problem page would be impossible to build, as would your example tree.

Your data is 1 2 3 4 5 6 7

The initial node is null, so the first node attached will have value 1, and 1 will be the root of your tree.

Based on your example, it looks like there's an assumption that the input is expected to be an ordered array, and thus that the root of any given (sub-)tree can be determined by simply taking the middle value. Something like this:

The problem should state that the input is in the order that the in-order traversal of the tree would yield, if that is the case.

Actual test case:

2

1 2 4 3 5 6 7

Output:

No

Let's test the in-order assumption:

1: We take the middle of {1 2 4 3 5 6 7}, which is 3, and it's the first node inserted, so it becomes the root

2: We take the middle of {1 2 4}, which is 2

3: 2 is less than 3, so we attach it to the left

4: We take the middle of {5 6 7}, which is 6

5: We take the middle of {1}, which is 1, and goes left of 2, and the middle of {4}, which is 4, and goes right of 2; we do the same for the right side of the array, and get:

And we see the problem - the (4) node is in the left sub-tree of the (3) node, which violates the binary search tree definition. Thus we return false, the stub code prints "No," and we have confirmed the assumption of the input order.

could you find the solution of your question

Here is my algorithm:

You would be fired right away from a real job if you ever create a piece of code like this. Google "magic numbers" antipattern

That was advice, no? I think he'd benefit from it - I even explained myself to extent. Leave your personal concerns out of it

If that is insulting to you, u'd be surely fired from our company with the speed of lightning

Sergei82, your comments are hard for me to read because they are much more concerned with tearing down coder2000 than educating him.

I attempted to explain why his comments weren't constructive, but he wasn't listening. This is why I deleted my comments. I agree with you and said something similar, but he kept thinking I was insulted by his comments. It's unfortunate to see that another developer is being so judgemental and using insults instead of working together to make other developers better. Fortunately, the people that are open to teaching and providing constructive feedback are the ones that end up making the largest impact, and become the best developers. Hopefully he will think about his actions and decide to turn his attitude around.

I wouldn't want to work at your company. You're a dick if you think making comments like that is ok.

if you talk like that to a colleague, you'd be fired right away. Google "professionalism" antipattern.

Due to the truly baffling nature of this code, I found it shocking that you passed the 10 test cases provided. This code does not work:

[5, 5, 7, 10, 12, 14, 15, 16, 18, 20] fails [1, 3, 6, 9, 10, 12, 15, 17, 19, 22] fails

Ah crap - I was scratching my head until I read your last point here. Then I went and read the problem again. Attention to detail is important! I fully missed "value of

every node"You can easily understand the order of Insertion in Binary Search Tree here: https://youtu.be/pHFhLNAn4Z0

I am confused. I know what the order of insertion in a Binary Search Tree is but the problem said "given the root node of a binary tree", not "given a root node of a binary search tree", so we can't assume the input will be inserted by the order of insertion in a BST. Besides, the objective of the problem is to verify if the Binary Tree given is a BST or not. If the binary tree is constructed with a BST's order of insertion, then the output will always be 'Yes'

In this video, Insertion video, watch from 3:35. And apply the same on the graph shown in the problem.