On 11/2/06,
Arunachalam <[EMAIL PROTECTED]> wrote:
Here are my interesting observations1) The first element of the BST will remain as the root.2) All the elements which are smaller than the root will go to the left of the root node.3) All the elements greater would go to the right of the root node.Right tree and left tree should be tested recursively based on the above condition.Guys. please post pseduocode and idea but not actual code. It will be really painful to get through the normal coding.You can constuct your algorithm based on this.regardsArunachalam.
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?????
--
===================================
want to know more about me
http"//ww.livejournal.com/users/arunachalam
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
