[algogeeks] Re: Balanced tree building

Sat, 18 Mar 2006 12:41:14 -0800

Another solution
 
node *oldtree;
 
node *build_new(N)
{
node *temp, *r;
int N1, N2;
 
if N==0 return NULL;
N1 = (N-1)/2; //no of node in the right subtree
N2 = N-1-N1; //no of node in the left subtree
 
temp = build_new(N1);
r = oldtree;
oldtree = oldtree->left;
r->right = temp;
r->left = build_new(N2);
return r;
}
 
main()
{
node *newtree;
N = no_of_node(oldtree);
newtree = build_new(N);
}

i think this solution fulfill all the criteria in the problem i.e. perfectly height balanced, O(N) time and O(logN) space complexity. plz check it. if there is a probem in this solution plz dont forget to mention it
i have really enjoyed this problem. thanx Gene for such good problem

On 3/19/06, Malay Bag <[EMAIL PROTECTED]> wrote:
> @rajiv..
> can you plz write the code or pseducode? i am not clear yet..
> thanx in advance
>
> On 3/19/06, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
> >
> > No, I guess you've misunderstood the logic.
> >
> > See, the idea is to build a max balanced tree.
> > For which,  we need to check the height of the tree
> > only the first time, there after we know what
> > the lengths of the left and right chains are
> > going to be.
> >
> > So, though your recursive formula looks right,
> >
> > >>>T(N) = 2T(N/2) + O(N) which results T(N) = O(NlogN)
> >
> > there is a subtle flaw in that, the O(N) isn't
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---

Reply via email to