If we can have the total no. of nodes in tree as an input (say N), this problem is pretty easy.
We construct a full BST of level = ceiling ( log (base 2) N ) - 1 conatining only dummy nodes. Now we travel the BST in the same fashion as a linked list starting from the root node. The root must have the highest number, so it becomes the right-most daughter of the right-most node of the last level of the full BST. This tree is then filled (filled in reverse inorder mode) with the numbers obtained from the list-list traversal of the original BST. While doing the traversal in the original tree, we can delete each node as we have passed through it. At the exhaution of the original tree this new tree will obviously be balanced as the original tree with dummy values was balanced and in the worst case there will be only one level more in the RHS of the root of the BST. This algorithm can be accomplished in O(N) time O(N/2) space. The only hitch is that we have to know the total no. of nodes at the beginning. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
