[Solved] Function to turn a Binary Tree into the sums of all nodes below each node; segmentation fault if I don’t create a new binary tree [closed]

Question

It is a nuisance when we have to create an MCVE from fragments of a program. However, it’s doable — it’s a pain, but doable.

Here’s my variation on your code. Of the 115 lines shown, 35 are what you wrote in the question — roughly. So, I had to create twice as much code to create a semi-plausible MCVE.

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

typedef struct ABin_s *ABin;
struct ABin_s
{
    int valor;
    ABin esq;
    ABin dir;
};

ABin somasAcA_OK(ABin a);
int getsums(ABin a);
ABin somasAcA(ABin a);

static ABin newABin(int valor, ABin esq, ABin dir)
{
    ABin ab = malloc(sizeof(*ab));
    if (ab == 0)
    {
        fprintf(stderr, "Failed to malloc %zu bytes\n", sizeof(*ab));
        exit(EXIT_FAILURE);
    }
    ab->valor = valor;
    ab->esq = esq;
    ab->dir = dir;
    return ab;
}

int getsums(ABin a)
{
    if (a == NULL)
        return 0;
    int esq = getsums(a->esq);
    int dir = getsums(a->dir);
    return(a->valor + esq + dir);
}

ABin somasAcA_OK(ABin a)
{
    ABin b, *res;
    res = &b;

    if (a != NULL)
    {
        b = newABin(getsums(a), NULL, NULL);
        b->esq = somasAcA_OK(a->esq);
        b->dir = somasAcA_OK(a->dir);
    }
    if (a == NULL)
        b = NULL;
    return *res;
}

ABin somasAcA(ABin a)
{   // Remove unused b
    if (a != NULL)
    {
        a->valor = getsums(a);
        a->esq = somasAcA(a->esq);
        a->dir = somasAcA(a->dir);
    }
    return a;
}

static void print_postorder(ABin node)
{
    if (node != 0)
    {
        print_postorder(node->esq);
        print_postorder(node->dir);
        printf("Valor = %d\n", node->valor);
    }
}

static void print_tree(const char *tag, ABin node)
{
    printf("Tree: %s\n", tag);
    print_postorder(node);
}

static void free_tree(ABin node)
{
    if (node != 0)
    {
        free_tree(node->esq);
        free_tree(node->dir);
        free(node);
    }
}

int main(void)
{
    ABin root = newABin(3, 0, 0);
    ABin esq = newABin(1, 0, 0);
    ABin dir = newABin(2, 0, 0);
    root->esq = esq;
    root->dir = dir;

    print_tree("Before", root);

    ABin eval = somasAcA(root);
    assert(eval == root);

    print_tree("After", root);

    eval = somasAcA_OK(root);
    assert(eval != root);

    print_tree("Second time", root);

    free(root);
    free(esq);
    free(dir);
    free_tree(eval);
}

I created somasAcA_OK() from your working function, marginally cleaning it up. My somasAcA() is your ‘non-working’ function, somewhat cleaned up. I don’t think I significantly changed the functionality of either. Note that the tree building code doesn’t attempt to use a function to build it — you’ve not shown such a function. It creates three nodes and links them manually.

The code compiles cleanly under GCC 6.1.0 on Mac OS X 10.11.5 with the command line:

$ gcc -O3 -g -std=c11 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes \
>     -Wold-style-definition -Werror abin.c -o abin
$

When run under valgrind, it gets a clean bill of health.

$ ./abin
Tree: Before
Valor = 1
Valor = 2
Valor = 3
Tree: After
Valor = 1
Valor = 2
Valor = 6
Tree: Second time
Valor = 1
Valor = 2
Valor = 6
$

On the basis of what I see, your second lot of code, the one that you claim fails, works correctly, but the one that you claim succeeds doesn’t actually do the addition (the last valor should be 9 on the second time).

I’m a bit dubious about the way your functions work. I’d expect the somasAcA() to be evaluating the sub-trees before summing the modified trees. That it works could be a side-effect of the minimal tree. Maybe you should be using:

ABin somasAcA(ABin a)
{
    if (a != NULL)
    {
        a->esq = somasAcA(a->esq);
        a->dir = somasAcA(a->dir);
        a->valor = getsums(a);
    }
    return a;
}

I’m not convinced that it needs to return a value, either, so with some collateral changes, you could use:

void somasAcA(ABin a)
{
    if (a != NULL)
    {
        somasAcA(a->esq);
        somasAcA(a->dir);
        a->valor = getsums(a);
    }
}

Extending the testing to more extensive trees is left as an exercise for someone with the correct tree-creation function code.

Accepted Answer