Converting an array into binary tree using C?

Question

I am trying to convert an integer array into a binary tree using C.

For example for an array a[10]={5,2,1,6,7,3,4} , the Binary tree should look like

    5    
   / \  
  2   1    
 /\   /\  
6  7  3  4    

I tried to convert using the following code

typedef struct btree    
{        
    int value;    
    struct btree *left;    
    struct btree *right;    
}Btree;    
void insert(Btree *t,int *a,int index,int n)    
{    
    t=(Btree *)malloc(sizeof(Btree));    
    if(index<n)    
    {    
        t->value=a[index];    
        insert(t->left,a,2*index,n);    
        insert(t->right,a,2*index+1,n);    
    }    
}    
int main(void) {    
    int a[100],i;    
    Btree *t;    
    for(i=0;i<10;i++)    
        scanf("%d",&a[i]);    
    insert(t,a,0,i+1);    
    return 0;    
}  

Can someone help me out with this problem?

Answer 1

There are several issues here:

• Your node allocation should go inside the conditional block in insert, otherwise you allocate memory for null nodes.
• You should initialise the left and right pointers to NULL in case the node is a leaf node and has no children.
• Most important. Your changes to the tree are lost. The pointer variables are local to the current instance of insert (which you call recursively) and don't transfer to earlier instances or to main. Pass a pointer to the node pointer.
• Consider using zero-base indices throughout; they are standard in C.

So, here's how it should work:

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

typedef struct btree {
    int value;
    struct btree *left;
    struct btree *right;
} Btree;

void insert(Btree **t, int *a, int index, int n)
{
    if (index < n) {
        *t = malloc(sizeof(**t));
        
        (*t)->value = a[index];
        (*t)->left = NULL;
        (*t)->right = NULL;
        
        insert(&(*t)->left, a, 2 * index + 1, n);
        insert(&(*t)->right, a, 2 * index + 2, n);
    }
}

void print(Btree *t, int level)
{
    if (t) {
        print(t->left, level + 1);
        printf("%*s->%d\n", 4*level, "", t->value);
        print(t->right, level + 1);
    }
}

int main(void)
{
    int a[] = {5, 2, 1, 6, 7, 3, 4};
    Btree *t;

    insert(&t, a, 0, 7);
    print(t, 0);

    // TODO: Clean up memory used by nodes

    return 0;
}

(I've replaced the scanf stuff with a hard-coded array. The code does not clean up the allocated memory, which it really should.)