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;

}

 

[Ben Pfaff]

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

Besides a few typos, I see no obvious defects in your solution,
but (at least for me) linked lists and binary trees are tricky.

Here is my solution, from GNU libavl:

/* Performs a compression transformation |count| times,
starting at |root|. */
static void
compress (struct bst_node *root, unsigned long count)
{
assert (root != NULL);

while (count--)
{
struct bst_node *red = root->bst_link[0];
struct bst_node *black = red->bst_link[0];

root->bst_link[0] = black;
red->bst_link[0] = black->bst_link[1];
black->bst_link[1] = red;
root = black;
}
}

/* Converts |tree|, which must be in the shape of a vine, into a balanced
tree. */
static void
vine_to_tree (struct bst_table *tree)
{
unsigned long vine; /* Number of nodes in main vine. */
unsigned long leaves; /* Nodes in incomplete bottom level, if any. */
int height; /* Height of produced balanced tree. */

leaves = tree->bst_count + 1;
for (;
{
unsigned long next = leaves & (leaves - 1);
if (next == 0)
break;
leaves = next;
}
leaves = tree->bst_count + 1 - leaves;

compress ((struct bst_node *) &tree->bst_root, leaves);

vine = tree->bst_count - leaves;
height = 1 + (leaves > 0);
while (vine > 1)
{
compress ((struct bst_node *) &tree->bst_root, vine / 2);
vine /= 2;
height++;
}
}