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 [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
