I'm trying to find the total number of nodes at a given depth in a N-ary tree, but I'm stuck.

This is the data structure:

typedef struct elem2 {
  int value;
  struct elem2 *firstChild;
  struct elem2 *sibling;
} NTree_node;

typedef NTree_node *NTree;

The following function should traverse recursively the tree and return a non-negative integer:

int NTree_depth_nodes(NTree T, int depth) {
  if (T == NULL) {
    /* empty tree -> depth is 0 */
    return 0;
  }
  if (depth == 0) {
    /* depth 0 means we only have the root */
    return 1;
  }

  int left = NTree_depth_nodes(T->firstChild, depth - 1);
  int right = NTree_depth_nodes(T->sibling, depth - 1);

  return 1   (left   right);
}

It runs but doesn't return the correct output since it's based on a similar function which works only for binary trees.

Any hints on what I could improve or change? I think I'm not really understanding what could be the right procedure.

CodePudding user response：

There are several issues:

1. in the second recursive call:

   int right = NTree_depth_nodes(T->sibling, depth - 1);
   

   ...the wrong depth is passed as argument. As you make the call for the sibling, you shouldn't decrease the value for the depth parameter: the siblings are at the same depth. So change to:

   int right = NTree_depth_nodes(T->sibling, depth);
   

2. When depth is zero, you shouldn't return immediately: there might be siblings to check, which would add to the count.

Here is a correction:

int NTree_depth_nodes(NTree T, int depth) {
  if (T == NULL) {
    /* empty tree -> depth is 0 */
    return 0;
  }

  int count = 0;
  if (depth == 0) {
    /* depth 0 means we have a node at the intended level */
    count  ;
  }

  count  = NTree_depth_nodes(T->firstChild, depth - 1);
  count  = NTree_depth_nodes(T->sibling, depth);

  return count;
}

I tested this code with the following driver code:

NTree node(int value) {
    NTree n = malloc(sizeof(NTree_node));
    n->sibling = NULL;
    n->firstChild = NULL;
    n->value = value;
    return n;
}

int main(void) {
    /* Create this tree:
             1
           / | \
          2  3  4
            /|  |\
           5 6  7 8
                |
                9
    */
    NTree root = node(1);
    root->firstChild = node(2);
    root->firstChild->sibling = node(3);
    root->firstChild->sibling->sibling = node(4);
    root->firstChild->sibling->firstChild = node(5);
    root->firstChild->sibling->firstChild->sibling = node(6);
    root->firstChild->sibling->sibling->firstChild = node(7);
    root->firstChild->sibling->sibling->firstChild->sibling = node(8);
    root->firstChild->sibling->sibling->firstChild->firstChild = node(9);

    for (int depth = 0; depth < 5; depth  ) {
        printf("At depth %d there are %d nodes.\n", depth, NTree_depth_nodes(root, depth));
    }
    return 0;
}

The output is:

At depth 0 there are 1 nodes.
At depth 1 there are 3 nodes.
At depth 2 there are 4 nodes.
At depth 3 there are 1 nodes.
At depth 4 there are 0 nodes.