A certain level of a binary tree to array

Question

I need to put inside an array, the values of a binary tree, but the thing is, I should only put inside the array the values that are at a certain depth. And it should output the number of elements inserted at the array.

I have made this:

int nivel2_(ABin a, int n, int v[], int level, int *i){
    int t;
    if(!a) return 0;

    if(n == level){
        v[(*i)++] = a->value;
        return 1;
    }else{
        t = nivel2_(a->left, n, v, level+1, i) + nivel2_(a->right, n, v, level+1, i);
    }

    return t;
}

int nivel2(ABin a, int n, int v[]){
    int k = 0;
    int *i;
    i = &k;

    return nivel2_(a, n, v, 1, i);
}

As I will keep changing the index recursively and only when we reach the depth we want, I thought of using a pointer, this way, when one part of the recursive folding happens it will change the value to all the other folding processes. Makes sense?

Structures:

typedef struct slist
{
    int value;
    struct slist* next;
} *SList;

typedef struct arvbin* ABin;
typedef struct arvbin
{
    int value;
    ABin right;
    ABin left;
} arvb;

DOES IT WORK?

Only when I want the elements of the first level of depth!

Calling like this:

 nivel2(tree2, 1, v);

Complete code

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

typedef struct slist
{
    int value;
    struct slist* next;
} *SList;

typedef struct arvbin* ABin;
typedef struct arvbin
{
    int value;
    ABin right;
    ABin left;
} arvb;


int nivel2_(ABin a, int n, int v[], int level, int *i){
    int t;
    if(!a) return 0;

    if(n == level){
        v[(*i)++] = a->value;
        return 1;
    }else{
        t = nivel2_(a->left, n, v, level+1, i) + nivel2_(a->right, n, v, level+1, i);
    }

    return t;
}

int nivel2(ABin a, int n, int v[]){
    int k = 0;
    int *i;
    i = &k;

    return nivel2_(a, n, v, 1, i);
}

void insertTree(ABin *tree, int val){
    if((*tree)==NULL){
        *tree = (ABin) malloc(sizeof(arvb));
        (*tree)->value = val;
        (*tree)->left = NULL;
        (*tree)->right = NULL;
        return;
    }
    else if(val > (*tree)->value)
    {
        insertTree(&((*tree)->right), val);
    }
    else if(val <= (*tree)->value)
    {
        insertTree(&((*tree)->left), val);
    }
    return;
}

int main(){

    int v[10] = {0};

    ABin tree2 = NULL;
    insertTree(&tree2, 22);
    insertTree(&tree2, 1);
    insertTree(&tree2, 3);

    nivel2(tree2, 1, v);

    int i;    
    for(i=0; i<5; i++){
        printf("%d\n", v[i]);
    }

    return 0;

}

What is `n` (the second argument to `nivel2()`) supposed to be? You don't use it for anything except passing it on during the recursion. — Ted Hopp, Jul 08 '15 at 03:56
@TedHopp It's the level from where i want the elements of the trees — skills, Jul 08 '15 at 03:57
Hm. I was thinking it might be the capacity of `v` (the third argument). Or can your code assume that `v` is always large enough? — Ted Hopp, Jul 08 '15 at 03:58
Taking in consideration the exercise, i think that we can assume that v is large enough. — skills, Jul 08 '15 at 04:00
Please describe why/how it doesn't work. And it's best if you provide an [MCVE](https://stackoverflow.com/help/mcve) showing the problem. That is, include a main that sets up the tree and makes the relevant function call that demonstrates the problem. — kaylum, Jul 08 '15 at 04:03
Please state the expected output and the actual output. The program looks correct to me. If you print the second level (n=2) you will get an output of 1. Which is exactly correct. Are you expecting it to print 1 and 3? If you draw the tree you will see that 3 is at the third level. — kaylum, Jul 08 '15 at 04:19
@AlanAu with my compilator, i get segmentation fault 11, if i try to use n=2 nivel2(tree2, 2, v); — skills, Jul 08 '15 at 04:25
You haven't shown the declaration of `tree2` in your code. I added that as a global which initialises it to NULL. Any chance your code declares `tree2` as a local in main and doesn't set it to NULL? That would cause a segfault (unless you are lucky and that stack variable happens to be 0). — kaylum, Jul 08 '15 at 04:29
@AlanAu even declaring it as NULL before adding elements to it, is giving me an instantaneous segmentation fault. But if you say it works, i will rest my case and call it a fault on the compilator, normally i work with gcc from linux, but i'm using a mac OS, sometimes it gives me SegFault where linux doesn't — skills, Jul 08 '15 at 04:37
So instead of a [list](http://stackoverflow.com/questions/31282495/create-linked-list-from-elements-of-a-binary-tree-at-a-certain-depth), you need to populate an array. And the list problem was a level-constrained version of converting a whole [tree to a list](http://stackoverflow.com/questions/31259665/convert-binary-tree-to-linked-list). Are you learning from your prior questions? Isn't managing an array much simpler than managing a list (or as simple as managing a list)? — Jonathan Leffler, Jul 08 '15 at 04:39
@JonathanLeffler it seems simpler, and my code makes sense to me :). I thought here at SOF people could help me pointing out where it does not make sense. — skills, Jul 08 '15 at 04:43
You included a complete example that's compilable; that's a good step in the right general direction. With the two headers, it compiles under pretty excruciatingly demanding compiler options without a witter (I added `static` before each function other than `main()` and used `int main(void) {` because my compilation options demand that, but your code was OK other than that). That's good! — Jonathan Leffler, Jul 08 '15 at 04:53
@skills Just to show it runs ok here's [the result I get](http://ideone.com/sTPUyY). — kaylum, Jul 08 '15 at 05:25
@AlanAu I'm really sorry for the confusion, but trust me, it does not compile in my MacOS , i've tried now with Linux and worked! I am sorry — skills, Jul 08 '15 at 06:00

score 2 · Accepted Answer · answered Jul 08 '15 at 05:13

The code looks mostly OK to me. Here's a mildly modified version, mainly with a tree printing function added, and some diagnostics, and an extended tree. My suspicion is that you expected your tree to have just 2 levels, but it actually had 3.

Code

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

typedef struct slist
{
    int value;
    struct slist* next;
} *SList;

typedef struct arvbin* ABin;
typedef struct arvbin
{
    int value;
    ABin right;
    ABin left;
} arvb;

static int nivel2_(ABin a, int n, int v[], int level, int *i)
{
    int t = 0;
    if (a)
    {
        if (n == level)
        {
            v[(*i)++] = a->value;
            t = 1;
        }
        else
        {
            t += nivel2_(a->left, n, v, level + 1, i);
            t += nivel2_(a->right, n, v, level + 1, i);
        }
    }

    return t;
}

static int nivel2(ABin a, int n, int v[])
{
    int k = 0;
    int r = nivel2_(a, n, v, 1, &k);
    printf("r = %d; k = %d\n", r, k);
    return k;
}

static
void insertTree(ABin *tree, int val)
{
    if ((*tree) == NULL)
    {
        *tree = (ABin) malloc(sizeof(arvb));
        (*tree)->value = val;
        (*tree)->left = NULL;
        (*tree)->right = NULL;
        return;
    }
    else if (val > (*tree)->value)
    {
        insertTree(&((*tree)->right), val);
    }
    else if (val <= (*tree)->value)
    {
        insertTree(&((*tree)->left), val);
    }
}

static void tree_to_array(ABin tree, int level)
{
    int v[10] = { 0 };
    int n = nivel2(tree, level, v);
    printf("Converted level %d to array:", level);
    for (int i = 0; i < n; i++)
        printf(" %d", v[i]);
    putchar('\n');
}

static void print_tree(ABin tree, int level)
{
    if (tree != 0)
    {
        printf("Level %d: %d\n", level, tree->value);
        print_tree(tree->left, level + 1);
        print_tree(tree->right, level + 1);
    }
}

int main(void)
{
    ABin tree2 = NULL;
    insertTree(&tree2, 22);
    insertTree(&tree2, 10);
    insertTree(&tree2, 13);
    insertTree(&tree2, 33);
    insertTree(&tree2, 39);
    insertTree(&tree2, 43);
    insertTree(&tree2, 19);

    print_tree(tree2, 1);

    for (int level = 1; level < 5; level++)
        tree_to_array(tree2, level);

    return 0;
}

Sample output

Level 1: 22
Level 2: 10
Level 3: 13
Level 4: 19
Level 2: 33
Level 3: 39
Level 4: 43
r = 1; k = 1
Converted level 1 to array: 22
r = 2; k = 2
Converted level 2 to array: 10 33
r = 2; k = 2
Converted level 3 to array: 13 39
r = 2; k = 2
Converted level 4 to array: 19 43

That looks correct to me for the tree shape that's printed.

i am sorry but using Mac OS it simply does not compile, giving me segmentation fault, will try to understand why latter on. I have tried the code using a Linux distro and it worked indeed. I am sorry for the trouble caused and thank you for the code improvement :) — skills, Jul 08 '15 at 06:01
That's odd; I compiled it on Mac OS X 10.10.4, admittedly using a home-built GCC 5.1.0, but I'd be astonished if there was anything in the code that varied between that and the XCode compiler — and a check compile suggests no problem. I did use `-std=c11`. In fact, I used: `gcc -O3 -g -std=c11 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes -Wold-style-definition -Werror t2a.c -o t2a`. Using [`valgrind`](http://www.valgrind.org/), it leaks the data in the tree (not surprising since it isn't freed), but is otherwise clean. — Jonathan Leffler, Jul 08 '15 at 06:03

A certain level of a binary tree to array

1 Answers1

Code

Sample output