this is not correct. its order sensitive. if u see his example L1 and L3 cannot be simply compared like strings. There can be many ways to have the same elements given in slightly different order yet produce the same BST. Im not sure why Ravi doesnt want to construct the BST. That wud give O(n) time easily. (but also O(n) memory)
For now, the only way I can think of, is by actually constructing the BST in some form.
Another way (O(n^2) time ) without constructing the BST can be formed by making this observation:
For an element L[i] in the list , see the next smaller element than L[i]. Call it L[j] .
If in both the lists for all i, order of L[i] and its corresponding L[j] are same (that is either L[i] comes first then L[j] or otherwise) then the lists give the same BST.
Sorry ,its hard for me to picturise it here. Correct me if this is wrong :)
On 11/2/06, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
:).
Apparently, Ravi has an assumption that each BST should be constructed
with same method. And the first one is choosen as a root.
In fact, if two lists have identical elements, they have identical BST
sets.
At least, if we focus on Ravi's problem, this problem will be reduced
to order comparison between two strings.
And it can be handled in O(N).
On Nov 1, 2:23 pm, "Vijendra Singh" <[EMAIL PROTECTED]> wrote:
> Oh ok.. I got confused... lemme think about this one. I think it has a
> recursive soltuion but will confirm it.
>
> -Vijju
>
> On 11/1/06, ravi <[EMAIL PROTECTED]> wrote:
>
>
>
> > I think u have misunderstood the question.
>
> > I am not asking about the two lists have identical elements or not?
>
> > If we have two lists then how will we check whther two lists produce
> > identical BSTs or not?
>
> > For example
>
> > L1 = { 10, 5, 15 }
> > L2 = { 5 , 10, 15 }
> > L3 = { 10, 15, 5 }
>
> > L1, L2, L3 all have identical elements.
> > But only L1, L3 will produce identical BSTs.
>
> > L1, L3 produce tree as 10
> > 5 15
>
> > L2 produce BST as 5
> > 10
> > 15
>
> > I think now the question is clear?????
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
