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.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Trees: Is This a Binary Search Tree?
You are viewing a single comment's thread. Return to all comments →
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.