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
i think either me or u have misunderstood the problem.> A list can be transformed to serveral BSTs A 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
Hi, the ones u mentioned are by property of BST. The original problem imposes a constraint on building the BST, so the recursive sol'n maynot work :)On 11/2/06,
Arunachalam <[EMAIL PROTECTED]> wrote:
Here are my interesting observations
1) The first element of the BST will remain as the root.
2)
Here are my interesting observations
1) 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 r
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 "I
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 elem
> In fact, if two lists have identical elements, they have identical BST sets. 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
:).
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 compari
you make no mention of time requirements, so you can do the following:
Since it seems you are using the first element as the root of the tree,
you can partition the list into two separate lists on either side of
the pivot - do the same on the other list, if the sub-lists have equal
numbers do this
Oh ok.. I got confused... lemme think about this one. I think it has a recursive soltuion but will confirm it.-VijjuOn 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 ho
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 hav
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, probably you meant a balanced BST, though even that might not be unique.so in my opinion, we just need to check if the two lists have identical elements, which
12 matches
Mail list logo
