A list can be transformed to serveral BSTs (If the number of elements
is n, then you can caculate the numbers of its BSTs). But, if we chose
a specified method or process (just as ravi supposed) to construct the
BST, then it will be unique. I have the same opinion with Vijendra
Singh. He said "If the two lists have same elements, then these *can*
produce identical BSTs. as for any list, there are number of ways to
construct a BST,"
And I believe the right solution should be the same way "arun kumar
manickan" provided. Its time complexity can be reduce to O(n) by
comparing the orders of each lists("String" in former post is a type
error).
I will put my program tomorrow in my time, as now I am kinda busy.
On Nov 2, 5:17 pm, Arun <[EMAIL PROTECTED]> wrote:
> > In fact, if two lists have identical elements, they have identical BSTsets.
> 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 algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
