Tree to List Problem

First of all, this is a homework related problem.
I'm trying to solve the Stanford Binary Tree to Doubly Linked List problem.
Tree List Recursion Problem
I'm kind of stumped...I don't get why it falls into a loop. It builds a tree that looks like this:
6
/ \
3 7
/ \ \
0 4 9
\ \ /
2 5 8
/
1

It makes it as far as setting the head to '0', descending to '1', then it loops between 0 and 1!

I don't understand why it doesn't return to '2'. If you could be so kind as to help me understand why. Is it a pointer problem? Do I not understand the recursive algorithm? Static variables?!
Just a nudge in the right direction, please.

Code:

 10 struct node
 11 {
 12     int data;
 13     struct node *small;
 14     struct node *large;
 15 };
 16 
 17 typedef struct node NODE;
 18 
 19 
 20 int main(void)
 21 {
 22     NODE *genTree(int *data);
 23     NODE *treeToList(NODE **current);
 24     void printTree(NODE *tree);
 25     void printList(NODE *list);
 26 
 27     NODE *tree, *list;
 28     int data[10] = {6, 3, 7, 0, 4, 9, 2, 5, 1, 8},
 29         i = 0;
 30 
 31     printf("Data:\n");
 32     for( ;i < 10; i++)
 33         printf("%d ", data[i]);
 34     printf("\n");
 35 
 36     tree = genTree(data);
 37     printf("Data in tree:\n");
 38     printTree(tree);
 39     printf("\n");
 40 
 41     list = treeToList(&tree);
 42     printf("Data in list:\n");
 43     printList(list);
 44     printf("\n");
 45 }
 46 
 47 NODE *treeToList(NODE **current)
 48 {
 49     void link(NODE *smaller, NODE *larger);
 50 
 51     static NODE *tail = NULL,
 52                 *head = NULL;
 53 
 54     if(!(*current)) return NULL;
 55 
 56     treeToList(&(*current)->small);
 57 
 58     if(!head)
 59         head = *current;
 60 
 61     if(tail != NULL)
 62         link(tail, *current);
 63 
 64     tail = *current;
 65 
 66     treeToList(&(*current)->large);
 67 
 68     link(tail, head);
 69 
 70     return head;
 71 }
 72 
 73 void link(NODE *small, NODE *large)
 74 {
 75     small->large = large;
 76     large->small = small;
 77 }

Start with an even smaller tree. In fact:

1. First ensure that it works with an empty tree.
2. Then make sure that it works with a tree containing only one item.
3. Then make sure it works with a tree with two items where the child is left of the root.
4. Then make sure it works with a tree with two items where the child is right of the root.
5. Then make sure it works with a balanced tree of three items.

It should be far easier to debug and find the problem that way.

Here's an observation though:
You're both using an in-out parameter and a return value, yet the recursive calls are ignoring the return value. Are you absolutely clear on which each of those is for, and are sure you're able to ignore the return values?

It's a tad disappointing that the assignment states that you must use recursion. There's an even more clever way of doing it in O(n), using iteration, and O(1) space.

In the future, please don't paste in line numbers from your editor. It makes it a pain for me to copy your code and get it compiling. And while we're on the subject, I can't compile and run your code because I'm missing the following functions:
undefined reference to `genTree'
undefined reference to `printTree'
undefined reference to `printList'

Without your print function, I can't say why it loops forever, but a guess would be that you have somehow created a list with only 2 elements, 0 and 1 in there, and you don't properly terminate your printing loop (remember, the list is circular).

Any reason you didn't read all the way through the assignment and look at the hints and sample solutions? You don't decompose the problem the way the assignment suggested and you call link in the wrong places. You actually use link (the assignment calls it join) where you should be using append to append the two sub lists.

There are also a couple obvious issues that, while they might not fix your code, should nevertheless be resolved:
1. Don't put function prototypes inside a function. Put them at the top of the file, between your typedef and your main function. If they will be used by code in a different translation unit (.c file), then you need a header file.
2. You don't need to pass a NODE ** into treeToList since you aren't trying to modify the address current points to in the calling scope (i.e. tree). Just make the parameter NODE * and call it like so: treeToList(tree). You will also be able to avoid unnecessary dereferencing, so all your uses of *current can be replaced with just current.

Thanks for the responses.
Anduril-- I updated the code with some corrections. I guess I missed hint #2, and I finally came to the conclusion that my code is algorithmically wrong. It's taking a lot not to peak at the solution...
I'll repost the code if and when I get it right.
sample.2.c

Alright, it works. I added an if statement.

sample.c

also...
:%s/^...//

Mad props for not looking at the solution, and also for coming up with your own algorithm that, unfortunately, only mostly works.

Actually, it works fine for the input you hard coded. It also works when I put the numbers in ascending order, from 0 to 9. It seg faulted when I put the numbers in descending order though. I ran it through a debugger and noticed that the list you built in treeToList wasn't circular, so printList did a node = node->large, when node->large was null, so on the next go round, tried to print NULL->data, which doesn't work. I don't feel like fully breaking down your algorithm right now to see if we can fix it, so I will help steer you toward the provided solution.

Lets look at some fundamentals that might help you turn your tree into a list:
1. Every node in a binary tree can be the root of a subtree, whose properties are the same as the whole tree. This is true even if it has no children (it will be a subtree of size one, a root only), and it is this fact that really helps us process trees recursively.
2. In an ordered binary tree (or subtree), any elements that are smaller than the root are located on it's left, or "small" branch. Similarly, any elements larger than a given root are located on the right, or "large" branch.
3. If you take a random element from an ordered (ascending) list, all nodes that are smaller are located to the left of that node in the list, while all larger elements are on the right.
4. When we process a tree recursively, we typically do three steps: process the root, process the left subtree and process the right subtree (the order of those three operations can change and determines whether it's a pre-, post- or in-order traversal).
5. You can stick any two linked lists together to form a larger linked list, and still maintain the order within each half of the new list.
6. A linked list with one node is still a linked list.

With those concepts in mind, can you begin to see how to decompose this problem? Treat each of the 3 parts of tree recursion separately, and build a list from all 3 parts. Then, combine your lists. As you fall back through your recursive lists you will see your tree transform into a linked list. Hopefully that helps you without giving too much away. Good luck and come back if you need more help.

Alright, I removed the if statement, as it was unnecessary. I defy you to tell me it doesn't solve the problem. I tried an ascending, a descending, and a couple of different sets of ints. The only problem that I can find now, is that it's difficult to tell what's happening by reading the code.

Thing is, I don't know where that bug was. It seems like it was in printList().
working:

Code:

void printList(NODE *node)
{
	NODE *head = node;
	
	do	
	{
		printf("%d ", node->data);
		node = node->large;
	}
	while(node != head);

	return;
}

not working:

Code:

void printList(NODE *list)
{
	NODE *node = list;
	
	do	
	{
		printf("%d ", node->data);
		node = node->large;
	}
	while(node != list);

	return;
}

What?! Am I totally confused?

Anyway, so would you say that what I wrote is an in-order traversal? It descends to the smallest and then links each next larger as the next and last in the list.
What then does a pre-order or post-order traversal look like?
Thanks.

Still haven't peeked at the given solution...I think I'm scared to.

Originally Posted by kellyjosephpric

Alright, I removed the if statement, as it was unnecessary.

What if statement? As a small side note, before I get into the big stuff, you correctly declared main to return an int, so please put a return 0 at the bottom of main. Also, you should have seen this as a warning from the compiler, if not (or even if you did and ignored it), please turn on all your warnings when you compile and make sure they're resolved.

I defy you to tell me it doesn't solve the problem.

Haha! I defy you! It doesn't solve the problem (at least not entirely). I actually agree that your general approach works, but there is some small bug causing your list to not always be circular. Perhaps it's the mysterious if statement you speak of, but I can only test the code you've posted, not whatever you changed. If you insert pre-ordered data into a binary tree you effectively have a linked list. If this data is ascending, you have every node going all the way down the right/large branch to be inserted at the bottom. If the data is descending, it goes all the way down the left/small side. Maybe this has something to do with it.

I tried an ascending, a descending, and a couple of different sets of ints. The only problem that I can find now, is that it's difficult to tell what's happening by reading the code.

I made the following change to your code in sample.c (post #5) to cause the crash:

Code:

    int data[10] = {6, 3, 7, 0, 4, 9, 2, 5, 1, 8},

becomes

Code:

    int data[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0},

I can follow the gist of your code just fine

Thing is, I don't know where that bug was. It seems like it was in printList().
working:

Code:

void printList(NODE *node)
{
	NODE *head = node;
	
	do	
	{
		printf("%d ", node->data);
		node = node->large;
	}
	while(node != head);

	return;
}

not working:

Code:

void printList(NODE *list)
{
	NODE *node = list;
	
	do	
	{
		printf("%d ", node->data);
		node = node->large;
	}
	while(node != list);

	return;
}

What?! Am I totally confused?

Probably. Those two pieces of code are identical, except for the names of the parameter and the local variable. Your implementation of printList does the job assuming you have a perfectly constructed list, but if something is awry, as it seems to be for the input data I mentioned above (your list isn't circular in that case), your program seg faults. I modified printList to look like this to show you the null pointers at the start and end of your list:

Code:

void printList(NODE *list)
{
    NODE *node = list;

    while (node) {
        printf("data: %d small: %p large: %p\n", node->data, node->small, node->large);
        node = node->large;
    }

    return;
}

Anyway, so would you say that what I wrote is an in-order traversal? It descends to the smallest and then links each next larger as the next and last in the list.

Yes. You process the current/root node IN between processing the left and right subtrees.

What then does a pre-order or post-order traversal look like?

Preorder:
process root // PRE processing of the subtrees
process left subtree
process right subtree

Preorder:
process left subtree
process right subtree
process root // POST processing of the subtrees

Originally Posted by kellyjosephpric

Thing is, I don't know where that bug was. It seems like it was in printList().
working:

Code:

void printList(NODE *node)
{
	NODE *head = node;
	
	do	
	{
		printf("%d ", node->data);
		node = node->large;
	}
	while(node != head);

	return;
}

not working:

Code:

void printList(NODE *list)
{
	NODE *node = list;
	
	do	
	{
		printf("%d ", node->data);
		node = node->large;
	}
	while(node != list);

	return;
}

Those two are indeed identical. If you run your program with one of those and change it to the other then it will perform exactly the same.
What you do have to be careful about though is that your lists link correctly in both directions. Make sure you verify this inside your print function.

Also, don't put a return; statement at the end of your void function. A void function always just returns when it reaches the end.

I'll give you another big hint:
Think of Merge Sort. The data is split into two halves, each half is sorted recursively, then a last step is used to merge the two sorted portions together. Try doing things in similar order to this.

Oh yeah, and the final solution is a little more of a pure or classic recursive solution, since it doesn't rely on static variables (which act like globals in your case) to keep state across the recursive calls. The provided solution is a little sleeker in this regard, but you fulfill the requirements of the problem description, so you should be fine.

I'm pretty happy about this. I think I finally listened to your suggestions. Thanks for all the help.

You're very welcome. Looks pretty good, but still going to bust you one one last thing. Make main return 0 at the end, or any integer for all I care (zero is traditionally "success"), but just make it return something! You even told the compiler you would return an int.