linked list

Given a pointer to the root of a tree in which a node could have many children, write a function to compute the following statistics.

The number of internal nodes, i.e., nodes with at least one child node.

The number of leaves, i.e., nodes without any child node.

The maximum branch factor, i.e., the maximum number of child nodes an internal node has.

The depth of the tree, i.e., the maximum number of edges along any path from the root to a leaf.

You need to finish function trace() to compute above statistics and write the answers into the struct Answer.

Note that the children of a node is given as a linked list, where each node in this list has a pointer to the children of this node.

#include

#include

typedef struct ChildList ChildList;

typedef struct Node {

ChildList *list;

} Node;

struct ChildList {

Node *node;

ChildList *next;

};

typedef struct Answer {

int InternalNode;

int Leaf;

int MaxBranchFactor;

int Depth;

} Answer;

void trace(Node *root, Answer *ans);

Node *newNode()

{

Node *ret = malloc(sizeof(Node));

ret->list = NULL;

return ret;

}

ChildList *newList(Node *node, ChildList *next)

{

ChildList *ret = malloc(sizeof(ChildList));

ret->node = node;

ret->next = next;

return ret;

}

int main()

{

//sample input

Node *root = newNode();

Node *n1= newNode(), *n2 = newNode(), *n3 = newNode(), *n4 = newNode(), *n5 = newNode(), *n6 = newNode();

ChildList *l3 = newList(n3, NULL), *l2 = newList(n2, l3), *l1 = newList(n1, l2);

ChildList *l5 = newList(n5, NULL), *l4 = newList(n4, l5), *l6 = newList(n6, NULL);

root->list = l1;

n2->list = l4;

n4->list = l6;

//end

Answer *ans = calloc(1, sizeof(Answer));

trace(root, ans);

printf("%d %d %d %d ", ans->InternalNode, ans->Leaf, ans->MaxBranchFactor, ans->Depth);

return 0;

}

sample output : 3 4 3 3

node node node null node node node null list null list null node null list auall list null