# 50074. Tree Statistics

## I'm a slow walker, but I never walk backwards.

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 write one file trace.c with one 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.

trace.h

123456789101112131415typedef 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);


main.c

1234567891011121314151617181920212223242526272829303132#include <stdio.h>#include <stdlib.h>#include "trace.h"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\n", ans->InternalNode, ans->Leaf, ans->MaxBranchFactor, ans->Depth);        return 0;}


## Compile

123gcc -std=c99 -O2 trace.c -cgcc -std=c99 -O2 main.c -cgcc -std=c99 -O2 main.o trace.o


## Input Format

A root pointer and a structure.

## Output Format

Four integers indicating internal node, leaf, maximum branch factor and depth numbers.

## Sample Output

3 4 3 3