@above
Also i would like to mention that the above algo considers equal
valued elements and assumes that the BST should have the following
property:
1) leftChild < = root
2) rightChild > root
On 30 Dec, 13:24, 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.
