Recursive function: for vs if

Question

In one of the C exercises I had to create a function for binary tree traversal with a given depth.

My first thought was to use a for loop (traverse_preorder_bad). Finally, I could complete the task with a variable initialization + if (traverse_preorder_working), but I am still struggling to understand why the for solution didn't work.

Could someone explain me the difference? Is there an elegant solution?

Code on Ideone

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

const int RANGE = 1000;

typedef struct node_t
{
    int data;
    struct node_t *left;
    struct node_t *right;
} node_t;

node_t *node_new(int data);
node_t *node_insert(node_t *tree, int data);
void traverse_preorder_working(node_t *tree, int depth);
void traverse_preorder_bad(node_t *tree, int depth);

int main(int argc, char *argv[])
{
    node_t *tree = NULL;

    // Random seed
    srand((unsigned) time(NULL));

    // Create the root node
    tree = node_new(rand() % RANGE);

    node_insert(tree, 5);
    node_insert(tree, 1);

    printf("Expected output:\n");
    traverse_preorder_working(tree, 10);

    printf("Bad output:\n");
    traverse_preorder_bad(tree, 10);

    return 0;
}

node_t *node_new(int data)
{
    node_t *tree;

    tree = malloc(sizeof(*tree));
    tree->left = NULL;
    tree->right = NULL;
    tree->data = data;

    return tree;
}

node_t *node_insert(node_t *tree, int data)
{
    if (!tree)
        return node_new(data);

    if (data == tree->data)
        return tree;
    if (data < tree->data)
        tree->left = node_insert(tree->left, data);
    else
        tree->right = node_insert(tree->right, data);

    return tree;
}

void traverse_preorder_working(node_t *tree, int depth)
{
    int i;

    if (!tree)
        return;

    printf("%d\n", tree->data);

    i = 1;
    if (tree->left && i <= depth)
    {
        traverse_preorder_working(tree->left, depth - i);
        i++;
    }

    i = 1;
    if (tree->right && i <= depth)
    {
        traverse_preorder_working(tree->right, depth - i);
        i++;
    }
}

void traverse_preorder_bad(node_t *tree, int depth)
{
    if (!tree)
        return;

    printf("%d\n", tree->data);

    for (int i = 1; tree->left && i <= depth; i++)
        traverse_preorder_bad(tree->left, depth - i);

    for (int i = 1; tree->right && i <= depth; i++)
        traverse_preorder_bad(tree->right, depth - i);
}

Answer 1

The problem is that traverse_preorder_working is correctly recursive, when visiting a node you call traverse_preorder_working recursively on the left subtree (and then right)

Instead traverse_preorder_bad is still recursive but it makes no sense, when you visit a node you then call traverse_preorder_bad n-times on the same subtree with a different depth.

If you check invocation tree for something like:

       a
      / \
     b   c
    / \ / \
    d e f g

You can see that traverse_preorder_working(a,5) goes traverse_preorder_working(b,4), traverse_preorder_working(d,3) .. while other function goes

traverse_preorder_bad(a,5),
traverse_preorder_bad(b,4), visit subtree
traverse_preorder_bad(b,3), visit subtree
traverse_preorder_bad(b,2), visit subtree
traverse_preorder_bad(b,1), visit subtree ...

from the same level of recursion, which means that each node will be visited multiple times with different depth limits; this doesn't happen in the first correct version.

If each invocation of traverse_preorder_bad should visit a node and start visiting both subtrees but inside the code you call visit recursively more than twice (which is the case, since you have a loop) then something is wrong.

Answer 2

The "for" version make no sense. You only want to print the tree for a given node once, so you should only call traverse on each node once.

Additionally, based on one of your comments in your post, I think you have some misunderstandings about your working function.

You have multiple checks for whether the tree is null (both as the current tree or as its children)

i ever only has a value of one while it is being used. You could simplify to

void traverse_preorder_working(node_t *tree, int depth){
    if(!tree || depth <= 0){
        return;
    }
    printf("%d\n", tree->data);
    traverse_preorder_working(tree->left, depth - 1);
    traverse_preorder_working(tree->right, depth - 1);
}

All of the checks to see if we not should explore a node - either because it doesn't exist or it is too deep - are done only once (at the start of the function), and not repeated twice for each child. No i variable that does nothing.