calculating total no of nodes is too easy... a single traverse through the tree will suffice... this will take linear time and hence will not increase runtime complexity....
On 3/14/06, BiGYaN <[EMAIL PROTECTED]> wrote: > > 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 [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 -~----------~----~----~----~------~----~------~--~---
