@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.
