@topcoder 1) For N <= 2 and not 3 its always a "YES"..
2) Also if u are OK with traversing the array twice i.e instead of a single run N we can do it 2*N.. Then we can do the following to intialize left and right properly instead of -+INF : 1) Scan the array to get the smallest and the greatest element.. 2) Assign left = (smallest - 1) and right = (greatest + 1), given the fact that smallest and greatest are not already at the integral boundaries.. On 30 Dec, 14:19, Lucifer <sourabhd2...@gmail.com> wrote: > Actually, the initial code that i have written could have written as > follows: > > int left = -INF; // or smallest integral value > int mid = 10; // greatest integral value > int right = +INF; > > int i = 0; > while (++i < N) > { > // Same as the previous code.. > > } > > I didn't take the above initialization approach as while writing > actual code i personally don't find -INF and +INF to be a good option > to initialize.. Also instead of -INF and +INF we could have replaced > it with smallest integral and greatest integral value but still I > don't prefer it until and unless the node values are not guaranteed to > be within a particular range... > > --------------------------- > > On 30 Dec, 14:14, Lucifer <sourabhd2...@gmail.com> wrote: > > > > > > > > > @topcoder.. > > > You are correct.. I just figured out that the N<=3 condition is not > > always correct.. > > > Below i have explained with example the code that will fix it: > > > Basically for N=3 , say the sequence is a , b, c.. > > Then the valid cases would be: > > > a < b < c > > a >= b >= c > > a < b , (b>=c and a < c) > > a >= b , ( b < c and c <= a) > > > as u can see.. for 4, 2, 6 > > 4 > 2 and ( 2 < 6 but 6 > 2) hence its invalid.. > > > if ( A[0] < A[1] ) > > { > > if ( (A[1] < A[2]) ) > > { > > left = A[0]; > > mid = A[1]; > > right= A[2]; > > } > > else if (A[1] >= A[2] && A[0] < A[2] ) > > { > > left = A[0]; > > mid = A[2]; > > right = A[1]; > > } > > else > > goto end; printf("NO");} > > > else > > { > > if (A[1] >= A[2]) > > { > > left = A[2]; > > mid = A[1]; > > right = A[0]; > > } > > else if ( (A[1] < A[2]) && (A[0] >= A[2]) ) > > { > > left = A[1]; > > mid = A[2]; > > right = A[0]; > > } > > else > > goto end; printf("No"); > > > } > > > // Replace the greatest, smallest and mid code with the above one and > > it shall work.. > > > On 30 Dec, 13:42, top coder <topcode...@gmail.com> wrote: > > > > @Lucifer > > > > Looks like Your algo works for all of the my test cases. I am not able > > > to find counter case. > > > > Also we should not Print "Yes" for N<=3 > > > > For eg: > > > > A = 4,2,6 > > > > Then 2 is a root with 4 as left child and 6 as right child. It > > > contains two childs and fails the case. > > > > On Dec 30, 1:26 pm, Lucifer <sourabhd2...@gmail.com> wrote: > > > > > @above > > > > > Also i would like to mention that the above algo considers equal > > > > valued elements and assumes that the BST should have the following > > > > property: > > > > > 1) leftChild < = root > > > > 2) rightChild > root > > > > > On 30 Dec, 13:24, Lucifer <sourabhd2...@gmail.com> wrote: > > > > > > @An idea... > > > > > > Let the array of integers be A[N].. > > > > > > If N < = 3, then the answer would be YES. > > > > > > If N > 3, then the following algo will follow: > > > > > // The algo is self explanatory as its just ensuring BST property > > > > > keeping in mind that a parent node has only one child... > > > > > > int left = smallest(A[0], A[1], A[2]) ; > > > > > int right = greatest(A[0], A[1], A[2] ; > > > > > int mid = A[0] + A[1] + A[2] - left - right; > > > > > > int i = 2; > > > > > > while ( ++i < N) > > > > > { > > > > > if (A[i] <= mid && A[i] > left) > > > > > { > > > > > mid = A[i]; > > > > > right = mid; > > > > > } > > > > > else if (A[i] > mid && A[i] <= right) > > > > > { > > > > > mid = A[i]; > > > > > left = mid; > > > > > } > > > > > else > > > > > break; > > > > > > } > > > > > > if ( i == N) > > > > > printf ("YES"); > > > > > else > > > > > print("NO"); > > > > > > On 30 Dec, 12:51, top coder <topcode...@gmail.com> wrote: > > > > > > > Input : You have been given a sequence of integers. > > > > > > Now without actually constructing BST from the given sequence of > > > > > > integers (assuming the sequence is pre-order) determine if each node > > > > > > of BST has single child (either left or right but not both). > > > > > > Output : YES if given integer sequence corresponds to such a BST. > > > > > > otherwise say NO. > > > > > > > Ex. Say NO for 16,10,8,9,29,27,22. > > > > > > Say YES for 10,19,17,14,15,16 > > > > > > > I know the algo O(N^2) as follows: > > > > > > For every node in array(traverse from left to right), > > > > > > all the other nodes must be less or all the nodes must be greater > > > > > > than it. > > > > > > > But interviewer is expecting O(N). Any ideas?- Hide quoted text - > > > > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.