Lets say DLL is sorted. We have to convert the DLL so basically its
the manipulation of pointers.
Can we do it recursively?
//n is the total number of nodes in the list.
// next corresponds to right and prev corresponds to left pointer.
Node * BuildBalBST(Node *head, int n)
{
if(!n)
return NULL; //no node
if(n==1) // single node
{
head->next = NULL;
head->prev = NULL;
return head;
}
Node *temp1,*temp2,*temp3 = head;
int i;
for(i=0;i<n/2;i++)
temp3= temp3->next;
temp1 = BuildBalBST(head,n/2);
temp2 = BuildBalBST(temp3->next,n/2 - (n+1)%2);
temp3->next = temp2;
temp3->prev = temp1;
return temp3;
}
In case, DLL is not sorted, sort it then using any algo and call
above.
Did i miss any case??
On Jul 18, 5:57 pm, radha krishnan <[email protected]>
wrote:
> Really MS asking garbage collection questions ? :P
> 2) if the DLL is not sorted then it takes O(n lgn ) to build the BST
> but the code looks so bloated if we write the code
>
>
>
> On Mon, Jul 18, 2011 at 4:59 AM, Balaji S <[email protected]> wrote:
>
> > Convert a binary tree to binary search tree inplace..
> > Convert a DLL to a binary search tree that is balanced.
> > Implement a C++ garbage collector efficiently
>
> > --
> > With Regards,
> > Balaji.S
>
> > --
> > 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?hl=en.- Hide quoted text -
>
> - Show quoted text -
--
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?hl=en.
