ctreedouble-pointern-ary-tree

N-ary tree in C, struggling with double pointers node connection


I am stuck with a leetcode problem on N-ary tree since last few hours. Could anyone please help me?

struct Node {
  int val;
  int numChildren;
  struct Node **children;
};

typedef struct Node node;

node *new_node(int numC, int data) {
    node *new_node = (node *)malloc(sizeof(node));

    if (new_node) {
        new_node->children = &new_node;
        new_node->numChildren = numC;
        new_node->val = data;
    }

    return new_node;
}

int main(void) {
    node *root = new_node(3, 1); 

    node *p1 = new_node(2, 3);
    node *p2 = new_node(0, 2);
    node *p3 = new_node(0, 4);
  
    root->children[0] = p1; //join p1 to root's 1st child
    root->children[1] = p2;
    root->children[2] = p3;

    node *p4 = new_node(0, 5);
    node *p5 = new_node(0, 6);
    
    root->children[0]->children[0] = p4; 
    root->children[0]->children[1] = p5; 

    printf("%d, \t %d, \t %d \n", root->children[0]->val, root->children[1]->val, root->children[2]->val);
    printf("%d, \t %d ", root->children[0]->children[0]->val, root->children[0]->children[1]->val);

    //preOrder (root);
}

I am expecting:

1, 3, 2, 4, 5, 6

The output is:

5, 6, 4
5, 6

my p4 and p5 pointer are overwriting p1 and p2. Why?


Solution

  • One of the problems is here:

    new_node->children = &new_node;
    

    Here you save a pointer to the local variable new_node. Once the function returns, the life-time of that variable will end and the pointer you have saved will become invalid.

    The next problem is here:

    root->children[1] = p2;
    root->children[2] = p3;
    

    Arrays in C are not dynamic, you can't add elements to an array. If the pointer was valid, it would point only to a single Node structure, which means that the only valid index is 0.

    Both of these issues, on their own, lead to undefined behavior.