@rajiv... everything is right. but i think there is small problem. in order to get the middle point of the chain you will need to traverse half of the chain. this will take linear time. so effectively it becomes T(N) = 2T(N/2) + O(N) which results T(N) = O(NlogN) plz check whether i am right
On 3/17/06, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: > > I think the problem can be solved using > tree rotations. > > So, we start with a left skewed tree > > 3 2 > / / \ > 2 ---> 1 3 > / > 1 > > Find out the total number of nodes initially, > can be done in O(n) time and O(1) space. > Once we know the number of nodes, rotate the > tree right, by n/2 positions. Each rotation > takes O(1) time. Now the left and right > subtrees have n/2 and n/2 nodes each. > (Plus or minus 1 node, forget about that!) > > Rotate the left subtree and right subtree > apropriately, recursively. > (One will be right and other left) > > This will work out to an O(n) time solution, > cos in the base case you'll have a subtree > of size 1 and that wont need to be rotated. > And the recursive stack will grow to atmost > O(lg n) size, the height of the tree at any > time during rotations. > > Well, it does seem to work! > > > > --~--~---------~--~----~------------~-------~--~----~ 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.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
