C recursively build tree using structure pointer

Question

I'm now implementing Barnes-Hut Algorithms for simulating N-body problem. I only want to ask about the building-tree part.

There are two functions I made to build the tree for it.

I recursively build the tree, and print the data of each node while building and everything seems correct, but when the program is back to the main function only the root of the tree and the child of the root stores the value. Other nodes' values are not stored, which is weird since I printed them during the recursion and they should have been stored.

Here's some part of the code with modification, which I thought where the problem might be in:

#include<...>
typedef struct node{
    int data;
    struct node *child1,*child2;
}Node;
Node root; // a global variable
int main(){
    .
    set_root_and_build(); // is called not only once cuz it's actually in a loop
    traverse(&root);
    .
}

Here's the function set_root_and_build():

I've set the child pointers to NULL, but didn't show it at first.

void set_root_and_build(){
    root.data = ...;
    ..// set child1 and child2 =NULL;
    build(&root,...); // ... part are values of data for it's child 
}

And build:

void build(Node *n,...){
    Node *new1, *new2 ;
    new1 = (Node*)malloc(sizeof(Node));
    new2 = (Node*)malloc(sizeof(Node));
    ... // (set data of new1 and new2 **,also their children are set NULL**)
    if(some condition holds for child1){ // else no link, so n->child1 should be NULL
        build(new1,...);
        n->child1 = new1;
        //for debugging, print data of n->child1 & and->child2
    }
    if(some condition holds for child2){ // else no link, so n->child2 should be NULL
        build(new2,...);
        n->child1 = new2;
        //for debugging, print data of n->child1 & and->child2
    }
}

Nodes in the tree may have 1~2 children, not all have 2 children here.

The program prints out the correct data when it's in build() function recursion, but when it is back to main function and calls traverse(), it fails due to a segmentation fault.

I tried to print everything in traverse() and found that only the root, and root.child1, root.child2 stores the value just as what I've mentioned.

Since I have to called build() several times, and even in parallel, new1 and new2 can't be defined as global variables. (but I don't think they cause the problem here).

Does anyone know where it goes wrong?

The traverse part with debugging info:

void traverse(Node n){
    ...//print out data of n
    if(n.child1!=NULL)
        traverse(*(n.child1))
    ...//same for child2
}

Answer 1

The problem in your tree traversal is that you certainly process the tree until you find a node pointer which is NULL.

Unfortunately when you create the nodes, these are not initialized neither with malloc() nor with new (it would be initialized with calloc() but this practice in cpp code is as bad as malloc()). So your traversal continues to loop/recurse in the neverland of random pointers.

I propose you to take benefit of cpp and change slightly your structure to:

struct Node {   // that's C++:  no need for typedef
    int data;
    struct node *child1,*child2;
    Node() : data(0), child1(nullptr), child2(nullptr) {} // Makes sure that every created are first initalized
};

And later get rid of your old mallocs. And structure the code to avoid unnecessary allocations:

if(some condition holds for child1){ // else no link, so n->child1 should be NULL
    new1=new Node; // if you init it here, no need to free in an else !!
    build(new1,...);
    n->child1 = new1;
    ...
}
if (... child2) { ... }

Be aware however that poitners allocated with new should be released with delete and note with free().

Edit: There is a mismatch in your code snippet:

traverse(&root);  // you send here a Node* 

void traverse(Node n){  // but your function defines an argument by value !
   ...
}

Check that you didn't overllok some warnings from the compiler, and that you have no abusive cast in your code.

Answer 2

You may not be properly setting the children of n when the condition does not hold. You might want this instead:

void set_root_and_build()
{
    root.data = ...;
    build(&root,...); // ... part are values of data for it's child 
}

void build(Node *n,...)
{
    n->child1 = n->child2 = NULL;

    Node *new1, *new2;
    new1 = (Node*) malloc(sizeof(Node));
    new2 = (Node*) malloc(sizeof(Node));

    // set data of new1 and new2 somehow (read from stdin?)

    if (some condition holds for new1) 
    {
        n->child1 = new1;
        build(n->child1,...);
        //for debugging, print data of n->child1
    }
    else
      free(new1);  // or whatever else you need to do to reclaim new1

    if (some condition holds for new2)
    {
        n->child2 = new2; 
        build(n->child2,...);
        //for debugging, print data of n->child2
    }
    else
      free(new2);  // or whatever else you need to do to reclaim new2
}

Of course, you should be checking the return values of malloc() and handling errors too.

Also, your traversal is a bit strange as it recurses by copy rather than reference. Do you have a good reason for doing that? If not, then maybe you want:

void traverse(Node *n)
{
    ...//print out data of n
    if (n->child1 != NULL)
        traverse(n->child1)
    ...//same for child2
}