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?
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.