@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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 [email protected].
> > To unsubscribe from this group, send email to
> > [email protected].
> > 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
