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

Question

I want to create a function to sum all nodes below a certain node including its own value, like this

  3                       6
 / \                     / \
1   2  would turn into  1   2

Link to the exercise in question: https://codeboard.io/projects/16280

Here's the defenition of ABin and the call for the function:

typedef struct nodo {
    int valor;
    struct nodo *esq, *dir;
} *ABin;

ABin somasAcA (ABin a);

This is the version that works, even though I don't like it because it creates a new binary tree:

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

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

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

And this is the version that gives me segmentation fault:

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

The thing is, if I put a->valor = getsums(a); in the middle I don't get segfault (but I get wrong values if the height of the tree is higher than 2). What is causing this segmentation fault and why can't I do this without creating a new bin tree? Thanks.

Also, if you're on a platform where you can use [`valgrind`](http://valgrind.org/), then use that — it will likely tell you what you're doing wrong. — Jonathan Leffler, Jun 06 '16 at 23:07
I exposed the error and said in which situations it happens. I know how to do this one way, and I know there is a better way, which is why I asked. How is this "not correctly asked"? — C. Rib, Jun 06 '16 at 23:08
In the second `somsAcA()`, you don't use `b` so you shouldn't define it. In the `getsums()`, you have odd handling of `esq` and `dir`; why not use `int esq = getsums(a->esq); int dir = getsums(a->dir);`? — Jonathan Leffler, Jun 06 '16 at 23:11
This is not correctly asked because we have to write functions like `newABin()`, deduce the data structure, how you create the tree, and create a dummy `main()` — then we might be able to reproduce the problem. The trouble is, we can't tell what you've done in the functions you've not shown, and that might be critical. That's why an MCVE is requested. — Jonathan Leffler, Jun 06 '16 at 23:14
You should also review [Is it a good idea to typedef pointers?](http://stackoverflow.com/questions/750178/is-it-a-good-idea-to-typedef-pointers) — Jonathan Leffler, Jun 06 '16 at 23:16
@JonathanLeffler I totally forgot to put the defenition of ABin, I apologize, edited my original post. And thanks. — C. Rib, Jun 07 '16 at 08:38

score 2 · Accepted Answer · answered Jun 07 '16 at 00:08

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.

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

1 Answers1