Recursion based on the above 3 stmt won't work .
* how do we know the root in level i , where i belongs to
{0,1,...depth-1} .
It looks like a problem of isomorphism how do we check for it
without constructing a tree.
Arun prasath N
On Nov 3, 3:16 am, Arun <[EMAIL PROTECTED]> wrote:
> i think either me or u have misunderstood the problem.> A list can be
> transformed to serveral BSTsA list will give only one BST. (First node is
> always root). There is only
> one way of consrtucting a BST. Isnt it? Again this will be badly balanced
> depending the order of elements in the list.
>
> > 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).this is wat i meant in my prev. mail :) although i think his second
> condition is redundant. I dont know, how u can achieve this O(n).
> O(n^2) is easy and maybe O(nlgn) by tweaking a sorting algorithm.
>
> On 11/2/06, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
>
>
>
>
>
> > 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?????- 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-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
