Level order insertion in binary tree

Question

We have to insert elements in a binary tree level-by-level, that is, for an array:

a = {1,2,3,4,5,6}

1st level = [1]
2nd level = [2, 3]
3rd level = [4, 5, 6]

I have worked out a code but it results in NULL tree every time.

struct node
{
    int data;
    struct node* left;
    struct node* right;
};

node* create(int x)
{
    node* tmp;
    tmp=(struct node *)malloc(sizeof(struct node));
    tmp->data=x;
    tmp->left=NULL;
    tmp->right=NULL;
    return tmp;
}

struct node* tree;

void insert(struct node* tree, int* a, int start, int n)
{
    int left =2*start+1;
    int right=2*start+2;
    if(left>n || right>n)
        return;
    if(tree==NULL)
    {
        tree=create(a[start]);
    }
    if(tree->left==NULL && tree->right==NULL)
    {
        if(left<n)
            tree->left=create(a[left]);
        if(right<n)
            tree->right=create(a[right]);
    }
    insert(tree->left,a,left,n);
    insert(tree->right,a,right,n);
}

What language are you using? (It should probably be a tag and mentioned in your question.) — Joshua Dwire, Nov 01 '12 at 02:38
Where is the code that calls insert( ) to insert passing in the values? — Mark Taylor, Nov 01 '12 at 02:43

score 1 · Accepted Answer · edited May 23 '17 at 12:27

1

You're passing tree by value; whoever calls insert still has a NULL pointer after insert returns. See What's the difference between passing by reference vs. passing by value? for some background.

edited May 23 '17 at 12:27

Community

1
1

answered Nov 01 '12 at 02:20

Jamey Sharp

8,363
2
29
42

I tried using a double pointer but it doesn't solve my problem. – A1604 Nov 01 '12 at 02:52
What specific changes did you make to your code when you tried using a double pointer? – Jamey Sharp Nov 01 '12 at 02:54
Replaced all instances of 'tree' by '*tree' in 'insert' function , passed tree by reference and replaced recursive calls by 'insert(&((*tree)->left),a,left,n); insert(&((*tree)->right),a,right,n); – A1604 Nov 01 '12 at 02:59
Hmm, that does sound like the right replacement, so it's a bit mysterious that it didn't work when you tried that. We'd probably need to see insert's caller in context, together with whatever code you used to test that you had the right tree at the end. I'd also recommend using a debugger to inspect the values of your variables as the program runs, or at least `printf` key values, to identify when the tree becomes unreferenced. – Jamey Sharp Nov 01 '12 at 03:06
Turns out I had misplaced one of the parentheses. It works well now. Thank You! – A1604 Nov 01 '12 at 03:21

Level order insertion in binary tree

1 Answers1