@atul.. I missed a question asked by u above. The answer to it as follows: /* bcozz every node should have single child then how should i interpret mid,left,right ?? */
Say the given sequence is 10,19,17,14,15,16, the corresponding BST would be : 10 19 17 14 15 16 mid is nothing the previously accessed element.. i.e if the current element is A[i] then mid points to A[i-1].. Left and Right define the range within which the value A[i-1] should be valid for a BST. Hence, while for a valid BST with only one child, node A[i] will lie between either of following: a) Left < A[i] <= mid i.e Left < A[i] <= A[i-1] b) mid < A[i] <= Right] i.e. A[i-1] < A[i] <= Right Using the above logic i have traced the example BST - 10,19,17,14,15,16 i A[i] Left Mid(A[i-1]) Right 0 10 -INF 10 +INF 1 19 10 19 +INF 2 17 10 17 19 3 14 10 14 17 4 15 14 15 17 5 16 15 16 17 As the if conditions inside the while loop passed for all the elements when accessed sequentially.. Hence, its a BST (having only one child).. ---------------------------------------------- Now tracing the above algo for 16,10,8,9,29,27,22. i A[i] Left Mid(A[i-1]) Right 0 16 -INF 16 +INF 1 10 -INF 10 16 2 8 -INF 8 10 3 9 8 9 10 4 29 // Here the while loop will break.. // as 29 doesn't lie between // either (8,9] or (9,10] 5 27 6 22 ----------------------------------------------------------- Finally u must wondering whether we actually need the variable 'mid' as its always A[i-1].. -:) Yes, you don't need the 'mid' variable.. Only 'left' and 'right' would be sufficient.. On 31 Dec, 10:54, Lucifer <sourabhd2...@gmail.com> wrote: > @topcoder.. > > As pointed u by earlier that 4 ,2, 6 doesn't work for the initial > code.. > The 1st solution that i gave to resolve it is still faulty.. it will > fail for 4 3 2 1.. basically increasing or decreasing set of nos.. > > // The second and 3rd approach would work fine.. i.e (-INF, +INF) and > (smallest -1 , greatest +1) > > The 1st approach of initialization fails because we are restricting > the max and min value that can held by the BST without knowing their > exact values.. Hence, for a completely sorted sequence of nos.(inc or > dec) it will fail.... > > I m putting the final code below to remove all confusion : > ------------------------------------------ > > int left = -INF; // or scan the array to get the smallest element > //and assign left to (smallest -1) assuming that > //smallest is not the min value that an integer can > hold. > > int right = +INF; // or scan the array to get the greatest element > //and assign left to (greatest +1) assuming > that > //greatest is not the max value that an integer > can hold. > int mid = A[0]; > > int i = 0; > > while ( ++i < N) > { > if (A[i] <= mid && A[i] > left) > { > right = mid; > mid = A[i]; > } > else if (A[i] > mid && A[i] <= right) > { > left = mid; > mid = A[i]; > } > else > break; > > } > > if(i == N) > printf("YES"); > else > printf("NO"); > > On 31 Dec, 10:19, Lucifer <sourabhd2...@gmail.com> wrote: > > > > > > > > > @above format got messed up and re-posting.. > > > while ( ++i < N) > > { > > if (A[i] <= mid && A[i] > left) > > { > > right = mid; > > mid = A[i]; > > } > > else if (A[i] > mid && A[i] <= right) > > { > > left = mid; > > mid = A[i]; > > } > > else > > break; > > > } > > > On 31 Dec, 10:17, Lucifer <sourabhd2...@gmail.com> wrote: > > > > @atul.. thanks for pointing out the editing mistake.. > > > > I have fixed the while loop below: > > > > while ( ++i < N){ if (A[i] <= mid && A[i] > left) { right = > > > mid; > > > mid = A[i]; } else if (A[i] > mid && A[i] <= right) { > > > left = mid; > > > mid = A[i]; } else break;} > > > > On 31 Dec, 01:45, atul anand <atul.87fri...@gmail.com> wrote: > > > > > while ( ++i < N) > > > > { > > > > if (A[i] <= mid && A[i] > left) > > > > { > > > > *mid = A[i]; // both mid and right will contain same value** > > > > right = mid;* > > > > > // right=mid; /* i guess this is what you want....*/ > > > > // mid=A[i] > > > > * > > > > * > > > > } > > > > else if (A[i] > mid && A[i] <= right) > > > > { > > > > *mid = A[i]; // * *// both mid and left will contain same > > > > value* > > > > * > > > > left = mid;* > > > > } > > > > else > > > > break; > > > > > } > > > > > bcozz every node should have single child then how should > > > > i interpret mid,left,right ?? > > > > > On Fri, Dec 30, 2011 at 1:54 PM, 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? > > > > > > -- > > > > > 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. -- 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.