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 recursively on each of the resulting sublists for each array.
The way you know that you have the same tree is by checking the roots as you do the recursion. If at any point they differ, or the sub lists are a different size (than their counterpart) then you know the property does not hold. Depending on your interpretation, this _is_ constructing the tree, but in-place. Note: The way you construct the sublists is critical here. they must be in teh same order as they were in the origial list. So for instance: 5 10 3 7 2 13 15 4 Will partition into: 3 2 4 - 5 - 10 7 13 15 Or the pivots will be meaningless. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
