LL TO BST

[puzzlecracker]

Do you see any problems with the following algorithm that converts Link
list to Binary Search tree. Can you think of a better solution?

node* LLtoBST(node *head, int num)
{

node *root=head;
int i, mid=(num+1)/2;

if(!head) return NULL;

if(n==1){
head->prev=NULL;
head->next=NULL;
}

else{
for (int i=0;i<mid;++i,root=root->next)
;
root->prev=LLtoBST(head, mid-1);
root->next=LLtoBST(root->next,mid-1);
}
return root;

}

 

[Howard]

Do you see any problems with the following algorithm that converts Link
list to Binary Search tree. >

Aside from the fact it won't compile, you mean?

Can you think of a better solution?

node* LLtoBST(node *head, int num)
{

node *root=head;
int i, mid=(num+1)/2;

Why do you declare i here? It's already declared as an int in the loop
below.

if(!head) return NULL;

This could be at the top, to save a couple steps.

if(n==1){

What's n? Did you mean num?

head->prev=NULL;
head->next=NULL;
}

else{
for (int i=0;i<mid;++i,root=root->next)
;
root->prev=LLtoBST(head, mid-1);

Suppose num is 4. Then mid = (4+1)/2 = 5/2 = 2. So, mid-1 is 1. So you're
going to point your "left" member to the original head of the list, with
only one member. But the loop above just moved the pointer to the third
item in the list, so you're going to lose the second item, aren't you? I
suspect that the num passed to this function needs to be mid, not mid-1.

But that's just for num==4. What about other values of num?

root->next=LLtoBST(root->next,mid-1);
}
return root;

}

Step through this on paper, carefully, for both odd and even values of num.

Then, once you have a good design, and have coded it so that ther's no
compile errors, step through it in the debugger and see if it does exactly
what your paper version did.

Also, you mention that you're creating a "Binary Search Tree". But you
don't say whether the linked list is sorted or not. If it isn't then your
tree isn't going to be sorted, either.

-Howard

 

[Joseph Turian]

pc:

You should also keep in mind that splitting it down the middle may not
guarantee the best amortized performance. It depends upon the
distribution of the queries.

For example, if you only have right children i.e. with the lowest
element at the root and the highest element as the (rightmost) leaf,
this will give the best performance if you're only looking up the
lowest element.

If I'm not mistaken, a balanced tree is desirable iff the queries are
uniformly distributed over the stored items (i.e. if there are no
queries for items that don't exist). If there are queries for items
that don't exist, then the analysis gets much hairier.

Joseph