50074. Tree Statistics

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

Task Description

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.

Header and Main Program

trace.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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);

samplesample

main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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

1
2
3
gcc -std=c99 -O2 trace.c -c
gcc -std=c99 -O2 main.c -c
gcc -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 Input

0.in0.in

Sample Output

3 4 3 3

Discussion