# tree to single linked list conversion

• 05-02-2008, 03:55 PM
unix
tree to single linked list conversion
Hi Everyone,

I was working to convert a binary search tree into a singly linked
list, so that i get a sorted singly linked list too, and this is the
logic...

root = single_r(root,NULL); // Caller invokes in this manner...
static node* gresult; // Global pointer used to hold
the new root.

struct node * single_r(struct node* root, struct node* parent)
{
static int flag = 0;

if(root == NULL)
return root;

if(root->lptr != NULL)
{
root = clockwise_rotation(root,parent);
}
else
{
if(flag == 0)
{
gresult = root;
flag = 1;
}
parent = root;
root = root->rptr;
}
single_r(root,parent);
return gresult;
}

struct node * clockwise_rotation(struct node * root,struct node *
parent)
{
struct node * temp_root;

if(root == NULL)
return NULL;

if(root->lptr == NULL)
return root;

temp_root = root->lptr;
root->lptr = temp_root->rptr;
temp_root->rptr = root;

if(parent != NULL)
{
parent->rptr = temp_root;
}
return temp_root;
}

I keep on rotating the left child of the current node and make it as
a new root node. I keep repeating this until there isn't any left
childs. Now i repeat this for the right child and so on...

But the problem is that i have to return the new root node to the
caller and currently i'm using a static flag to serve this purpose.
But i want to avoid this as this doesn't fit well in multi-threaded
applications. Is there any way to solve without using static variables
and global variables and without iterations?

Thanks in advance ! ! !
• 05-02-2008, 05:48 PM
unix
Re: tree to single linked list conversion
Rahul <sam_cit@yahoo.co.in> writes:[color=blue]
>Hi Everyone,
>
> I was working to convert a binary search tree into a singly linked
>list, so that i get a sorted singly linked list too, and this is the
>logic...[/color]
[color=blue]
>Thanks in advance ! ! ![/color]

Do a google search on recursion. Look for algorithms for pre-order,
in-order and post-order tree walkers.

scott
• 05-03-2008, 11:30 AM
unix
Re: tree to single linked list conversion
On May 2, 10:48 pm, sc...@slp53.sl.home (Scott Lurndal) wrote:[color=blue]
> Rahul <sam_...@yahoo.co.in> writes:[color=green]
> >Hi Everyone,[/color]
>[color=green]
> > I was working to convert a binary search tree into a singly linked
> >list, so that i get a sorted singly linked list too, and this is the
> >logic...
> >Thanks in advance ! ! ![/color]
>
> Do a google search on recursion. Look for algorithms for pre-order,
> in-order and post-order tree walkers.
>
> scott[/color]

I knew that an inorder traversal of binary search tree would give me
the sorted list... but i can't change the links in them...
I wanted to have an in-place sorted list given a binary search tree...
• 05-04-2008, 12:52 AM
unix
Re: tree to single linked list conversion
Rahul wrote:[color=blue]
> Hi Everyone,
>
> I was working to convert a binary search tree into a singly linked
> list, so that i get a sorted singly linked list too, and this is the
> logic...
>
> root = single_r(root,NULL); // Caller invokes in this manner...
> static node* gresult; // Global pointer used to hold
> the new root.[/color]

[color=blue]
> I keep on rotating the left child of the current node and make it as
> a new root node. I keep repeating this until there isn't any left
> childs. Now i repeat this for the right child and so on...
>
> But the problem is that i have to return the new root node to the
> caller and currently i'm using a static flag to serve this purpose.
> But i want to avoid this as this doesn't fit well in multi-threaded
> applications. Is there any way to solve without using static variables
> and global variables and without iterations?[/color]

In general, you can always solve problems of this form in a mechanical
manner by making a temporary variable (usually a lexically-scoped local
variable) and then passing a pointer to that local variable into the
recursive function. Then you've replaced the global with a local.

For example, consider this node counting function that uses a global
variable:

int count; /* global */

void count_nodes(node* root) {
if (root == NULL) { return; }

count++;
count_nodes(root->left);
count_nodes(root->right);
}

void caller() {
count = 0;
count_nodes(sometree);
printf("there were %d nodes\n", count);
}

You can replace the above code with this:

void count_nodes_inner(node* root, int* count_ptr) {
if (root == NULL) { return; }

(*count_ptr)++;
count_nodes_inner(root->left, count_ptr);
count_nodes_inner(root->right, count_ptr);
}

int count_nodes_outer(node* root) {
int count = 0;

count_nodes_inner(root, & count);
}

void caller() {
printf("there were %d nodes\n", count_nodes_outer(sometree));
}

Often there is a better solution, but in the rare case that there isn't,
something like the above can always be used to eliminate the global
variable.

By the way, one object-oriented approach to solving this problem is to
create a class called something like TreeToListConversion. Then have a
method to do the conversion. The temporary state necessary during the
conversion can be stored in the fields of the object. It would be a
fairly short-lived object, but often that's OK.

- Logan