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.