recursion and traversing a binomial tree

Question

I have the following tree structure:

this one shows 3 levels. My actual problem will have 8 to 12 levels. I have the following program that I believe will traverse the tree in the right order. Two children nodes report to a parent node. If we know both children we can find the parent. Essentially we want to traverse the tree from right to left and from bottom to top. The numbers indicate the order the nodes need to be traversed.

Here's my code that I believe will accomplish this:

#include <stdio.h>

int main(void)
{
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            for (int k = 0; k < 2; k++)
            {
                printf("k loop: %d   ", i * 7 + j * 3 + k);
            }
            printf("\n");
            printf("j loop: %d  \n", i * 7 + j * 3 + 2);
        }
        printf("i loop: %d  \n", i * 7 + 6);
    }
    printf("final node: %d\n", 2 * 2 * 2 * 2 - 2);
}

This isn't very pretty and not very scalable as I would need to add another for loop for each additional level.

three questions:

1. how would I do this with recursion?
2. Is there a more scalable way of doing this without recursion?
3. which will be faster a for loop approach or a recursion approach

Answer 1

You can do this recursively with these steps for p(n, level):

• if level > 0, first print the substrees with
  • call n = p(n, level - 1) for the left subtree
  • call n = p(n, level - 1) for the right subtree
• then print n and return n+1

Here is a naive implementation:

#include <stdio.h>

int p(int n, int level) {
    if (level > 0) {
        n = p(n, level - 1);
        n = p(n, level - 1);
    }
    printf("%i\n", n);
    return n + 1;
}

// initial call for a depth of 8:
int main() {
    p(0, 8);
    return 0;
}