How does this recursion function in BST returns a linked list which is in-order?

Question

How does this recursion function in BST returns a linked list which is in-order?

Given: (Structure)

typedef struct TreeNode
{
    struct TreeNode *left ;  //left child
    struct TreeNode *right ;     //right child
    struct TreeNode *next ;  //field for linked list in tree
    Data Node_info;             //info data in node
} TreeNode;

Let's assume we have a BST with the numbers 3,2,4. (3 is root, 2 is left child, 4 is right child)

I have 2 functions which do the SAME, they create a linked list from the BST. I fail to follow up the recursion here, if anyone can help me figure it out, it would be awesome!

First function:

void  what1(TreeNode **head, TreeNode *root)
{
     if(root == NULL) 
           return; 
     what1((head),root->right);
     root->next=(*head);
     (*head)=root;
     what1((head),root->left);
}

My calculations: Go to right sub-tree until we reach null, return , make 4->next point on NULL, make head point on 4, then go left, return to 4, return again to 1, now 3->next point on 4, and make head point on 4, and so on..

But I still lack the understand when other functions are "on-hold" and when are they executed, meaning that my calculations are not accurate and I fail to follow up the function properly, which means I have somewhere lack of recursion understanding.

Here's the second function which I have absolutely NO IDEA how to follow it, which actually does the same thing. If you can help me with any of these functions, it would be greatly appreciated as I'm trying to fully understanding recursion with BST. I'm posting here many questions about this until I understand this completely.

TreeNode * what2(TreeNode *root)
{
    TreeNode *left = NULL, *right = NULL, *tmp = root;
    if (root != NULL) 
    {      
        left = what2(root->left);      
        right = what2(root->right);      
        root->next = right;      
        if (left != NULL)
        {
            tmp=left;  
            while (left->next != NULL)              
                left=left->next;         
            left->next=root;      
        }   
    } 
    return tmp;
}   

Answer 1

You're right in how the first function is working, you build the tree basically from end to beginning.

To understand the second one, all you have to notice is that it will create a list in the sub trees, and then combine the two lists. When you call the function, the following steps happen:

1. Get the head of the list created from the left node alone
2. Get the head of the list created from the right node alone
3. Attach the root node by setting the end of the left list to point to root, then have root point to the beginning of the right list.

This can be seen by

1.

left = what2(root->left);

In your example, this will simply return the left node because it is alone, however this happens because left->left and left->right are NULL for the left node, so it simply returns left.

2.

right = what2(root->right);

Same thing happens here, but with the right node.

3.

root->next = right;      
if (left != NULL)
{
    tmp=left;  
    while (left->next != NULL)              
        left=left->next;         
    left->next=root;      
} 

Here, we first set root->next to right so that we basically have the middle of the list created. Then, set tmp to left because it's going to be the head of the list (left-most, so beginning). Then traverse through the left list until we can set the last element to root. This creates a continuous list from left to root to right, so in-order.

Answer 2

This is for what1.

Here, head is a Node ** - which means that:

head   : is a : pointer to a pointer to TreeNode
*head  : is a : pointer to a TreeNode
**head : is a : TreeNode

Now when what1 this is called from main (or some other function) it is called like this:

/* Suppose root points to root TreeNode in tree */

/* ll_head will point to first node in linked list */
TreeNode *ll_head = NULL;

/* Call what1 and pass address of ll_head so that
 * address of the first node in linked_list can be stored in ll_head
 */  
what1(&ll_head, root);

Now see what happens when what1(&llhead, root), (i.e. what1(&ll_head, node 3)) is called:

When what1(&ll_head, node 3) is called, it does the following:

1. Calls (&ll_head, node 4)
2. Does some processing for node 3
3. Calls (&ll_head, node 2)

Lets see them one by one:

1. In node 4

4->next = (*head) /* which right now is pointing to NULL */ 
(*head) /* which is ll_head in main */ = address of node 4 

So, by now:

4->next = NULL, and 
(*head) /* which is ll_head in main */ =  address of node 4

2. Processing In node 3

3->next = (*head) /* which right now is pointing to node 4 */
(*head) /* which is ll_head in main */ = address of node 3

So, by now:

4->next is NULL,
3->next = address of node 4, and
(*head) /* which is ll_head in main */  = address of node 3

3. In node 2

2->next = (*head) /* which right now is pointing to node 3 */
3->next = address of node 4
4->next = NULL, and
(*head) /* which is ll_head in main */  = address of node 2

So when what1(*ll_head, node3) returns this will be the state of things:

ll_head = address of node 2
2->next = address of node 3
3->next = address of node 4
4->next = NULL

Which is the in order linked list of this BST.