Rahul writes:
>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...

>Thanks in advance ! ! !

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

scott

On May 2, 10:48 pm, sc...@slp53.sl.home (Scott Lurndal) wrote:
> Rahul writes:
> >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...
> >Thanks in advance ! ! !
>
> Do a google search on recursion. Look for algorithms for pre-order,
> in-order and post-order tree walkers.
>
> scott

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...

Rahul wrote:
> 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.


> 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?

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