Actually, the initial code that i have written could have written as
follows:
int left = -INF; // or smallest integral value
int mid = 10; // greatest integral value
int right = +INF;
int i = 0;
while (++i < N)
{
// Same as the previous code..
}
I didn't take the above initialization approach as while writing
actual code i personally don't find -INF and +INF to be a good option
to initialize.. Also instead of -INF and +INF we could have replaced
it with smallest integral and greatest integral value but still I
don't prefer it until and unless the node values are not guaranteed to
be within a particular range...
---------------------------
On 30 Dec, 14:14, Lucifer <[email protected]> wrote:
> @topcoder..
>
> You are correct.. I just figured out that the N<=3 condition is not
> always correct..
>
> Below i have explained with example the code that will fix it:
>
> Basically for N=3 , say the sequence is a , b, c..
> Then the valid cases would be:
>
> a < b < c
> a >= b >= c
> a < b , (b>=c and a < c)
> a >= b , ( b < c and c <= a)
>
> as u can see.. for 4, 2, 6
> 4 > 2 and ( 2 < 6 but 6 > 2) hence its invalid..
>
> if ( A[0] < A[1] )
> {
> if ( (A[1] < A[2]) )
> {
> left = A[0];
> mid = A[1];
> right= A[2];
> }
> else if (A[1] >= A[2] && A[0] < A[2] )
> {
> left = A[0];
> mid = A[2];
> right = A[1];
> }
> else
> goto end; printf("NO");}
>
> else
> {
> if (A[1] >= A[2])
> {
> left = A[2];
> mid = A[1];
> right = A[0];
> }
> else if ( (A[1] < A[2]) && (A[0] >= A[2]) )
> {
> left = A[1];
> mid = A[2];
> right = A[0];
> }
> else
> goto end; printf("No");
>
> }
>
> // Replace the greatest, smallest and mid code with the above one and
> it shall work..
>
> On 30 Dec, 13:42, top coder <[email protected]> wrote:
>
>
>
>
>
>
>
> > @Lucifer
>
> > Looks like Your algo works for all of the my test cases. I am not able
> > to find counter case.
>
> > Also we should not Print "Yes" for N<=3
>
> > For eg:
>
> > A = 4,2,6
>
> > Then 2 is a root with 4 as left child and 6 as right child. It
> > contains two childs and fails the case.
>
> > On Dec 30, 1:26 pm, Lucifer <[email protected]> wrote:
>
> > > @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 <[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?- Hide quoted text -
>
> > > - Show quoted text -
--
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.
