Hi Malay,
I don't see how you algorithm takes O(n) time or O(logn) space, The use of recursion should take into account the implicit stack.
for(int i = 0; i < n; i++)
process(height - 1)
itself transforms into recurrence T(n) = nT(n - 1) + O(1)
You will see that this is exponential (forget about linear, its not even polynomial). Also the space requirement is n + n - 1 + n - 2....1 = O(nexp2)
Most importantly, I am not convinced about the correctness of the algorithm.
For a chain of considerable length yours will contine you to be unbalanced except that most of the nodes will have left and right children, a simple test per your algorithm the root of the original chain continues to be the root of the final result, which is not true.
Thanks & Regards,
Padmanabhan
On 3/13/06, Malay Bag <[EMAIL PROTECTED]> wrote:
node *root;
node * build(int height)
{
node *r, *temp;
for(i=1, r=null; i<=height && root; i++)
{
temp = root;
root=root->left;
temp->right=r;
r=temp;
r->left = build(i-1);
}
return r;
}
void main()
{
node *tree;
tree = buld(n); // n=height of of new tree
}
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
