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;
}

Answer 2

1. What you're looking for is called an In-Order Traversal. It is generally independent of the number of levels in your tree because it is a type of Depth-First Traversal.

It generally follows the following algorithm

1. Recursively traverse left subtree
2. Visit root node
3. Recursively traverse right subtree

Here is a link for more information

---

2. It is entirely possible, and generally recommended, to use iterative methods of tree traversal. Although for small trees it's effects aren't really felt, for large recursive traversal takes up exponential amounts of memory space. Here is an example of in-order traversal using a stack on geekforgeeks

---

3. Although you won't notice it on a small tree, recursive approach is always slower than iteration.