Thread: 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 }

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

Alright, it works. I added an if statement.

Attachment 10207

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

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.