Making a linked list from a binary tree using Preorder Traversal

Question

I want to add elements to a Linked List while Preorder Traversaling on a Binary Tree. I do not want to destroy the BT, just make a copy of the elements in a linked list. This is my code snippet.

void Preorder(treeNode *node, Nodelist * head){
    if(node==NULL){
        return;
    }
    //printf("%d\n", node->data);
    head = List_insert(head, node->data);
    Preorder(node->left, head);
    Preorder(node->right, head);
}

Nodelist * List_insert(Nodelist * head, int v)
{
    Nodelist * p = Node_construct(v);
    p->depth = 2222;
    p -> next = head;
    return p;
}

void List_print(Nodelist * head)
{
    while (head != NULL)
    {
        printf("%d ", head -> value);
        printf("%d ", head -> depth);
        printf("\n");
        head = head -> next;
    }
    printf("\n\n");
}

treeNode * Insert(treeNode *node,int data)
{
        if(node==NULL)
        {
                treeNode *temp;
                temp = (treeNode *)malloc(sizeof(treeNode));
                temp -> data = data;
                temp -> left = temp -> right = NULL;
                return temp;
        }

        if(data >(node->data))
        {
                node->right = Insert(node->right,data);
        }
        else if(data < (node->data))
        {
                node->left = Insert(node->left,data);
        }
        return node;

}

int main(int argc, char**argv) {
        treeNode *root = NULL;
        root = Insert(root, 14);
        root = Insert(root, 15);
        root = Insert(root, 4);
        root = Insert(root, 9);
        root = Insert(root, 7);
        root = Insert(root, 18);
        root = Insert(root, 3);
        root = Insert(root, 5);
        root = Insert(root, 16);
        root = Insert(root, 20);
        root = Insert(root, 17); 

        Nodelist * head = NULL;
        Preorder(root, head);
        List_print(head);

    return 0;
}

The above code prints nothing. I think the problem is with the use of head = List_insert(head, node->data); in the preorder function. Any help with be appreciated.

Answer 1

You are passing NULL to the Preorder as the list head. This is passed by value and you cannot alter the head in the main function this way. Instead define Preorder like this:

void Preorder(treeNode *node, Nodelist **head)

So that you can do:

*head = Linst_insert....

inside the function to modify the list. Of course, you need to call preorder from the main function like this:

Preorder(root, &head);

Answer 2

Try this ... hope helps

Nodelist *Preorder(treeNode *node, Nodelist ** tail) { // use name 'tail' instead of 'head' because you are inserting on the tail, but this functions returns head..

    Nodelist *head;

    if(node==NULL){
        return;
    }
    //printf("%d\n", node->data);
    head = List_insert(tail, node->data);
    Preorder(node->left, tail);
    Preorder(node->right, tail);
    return head;
}

Nodelist * List_insert(Nodelist ** tail, int v)
{
    Nodelist * p = Node_construct(v);
    p->depth = 2222;
    p->next = NULL;
    if (!tail) {
        *tail = p;  // (*tail) is NULL, true when first time List_Insert called
    }
    else {
        (*tail)->next = p;
    }
    return p;
}

int main(int argc, char**argv) {
        treeNode *root = NULL;
        root = Insert(root, 14);
        root = Insert(root, 15);
        root = Insert(root, 4);
        root = Insert(root, 9);
        root = Insert(root, 7);
        root = Insert(root, 18);
        root = Insert(root, 3);
        root = Insert(root, 5);
        root = Insert(root, 16);
        root = Insert(root, 20);
        root = Insert(root, 17); 

        Nodelist * head = NULL;
        head = Preorder(root, &head);
        List_print(head);

    return 0;
}