Hi,
We can make the following observations :
1) Both arrays A and B should have same no of elements
2) First element of both A and B should be the same
3) All elements less than the first element in array A should come in the same order in array B also.
4) All elements less than the second element in array A should come in the same order in array B also.
Writing it more formally :
bool EquivalentBST ( array A , array B )
if ( A.length != B.length )
return false;
if ( A[0] != B[0] )
return false;
int l1 = 0; // index into the Array B , pointing to next smaller element
int g1 = 0; // index into the Array B , pointing to next greater element
for ( int i=1; i< A.length; i++){
if( A[i] > A[0] ) {
l1++;
while ( l1 < B.length && B[l1] > A[0] )
l1 ++;
if( l1 == B.length )
return false;
if ( A[i] != B[l1] )
return false;
}
else{
g1++;
while ( g1 < B.length && B[g1] > A[0] )
g1 ++;
if( g1 == B.length )
return false;
if ( A[i] != B[g1] )
return false;
}
}
return true;
End;
Correct me if I am wrong .
Arun.
The way a problem is solved is generally much more important than the solution itself.
--~--~---------~--~----~------------~-------~--~----~
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-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
