@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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[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.
