Inserting element in binary tree using pointers

**Ajay.Kumar** · 09-07-2014

Hey

This is my first post on this site.

I want to insert an element into binary tree using pointer passing through functions.

In my program i have used three structure which are follows :-

Code:

struct tree{
    int data1;
    struct tree *leftptr;
    struct tree *rightptr;
};


struct list{
    struct tree **data;
    struct list *node;
};


struct queue{
    struct list *front;
    struct list *rear;
};


void Insertintree(struct tree **root1,int data){
    struct tree *new=malloc(sizeof(struct tree));
    struct tree *cur=NULL;
    struct tree *n2;
    struct queue *q=malloc(sizeof(struct queue));
    q->front=NULL;
    q->rear=NULL;    
    if(!new&&!q){
        printf("Memory Error");
        return ;
    }


        new->data1=data;
        new->leftptr=NULL;
        new->rightptr=NULL;


    if(*root1==NULL){
        *root1=new;
        return;
    }


    enqueue(q,root1);
    while(q->front)
    {
        cur=dequeue(q);        
        if(!cur->leftptr||!cur->rightptr){
            if(!cur->leftptr)
            cur->leftptr=new;
            else
            cur->rightptr=new;
//            printf("%d",new->data1);
//            deletequeue(q);            
            break;
        }
        else
        {
            printf("In else while");
            if(cur->leftptr){
                n2=malloc(sizeof(struct tree));            
                n2=NULL;
                n2=cur->leftptr;
                enqueue(q,&n2);
            //    printf("%p",&(cur->leftptr));
            }
            if(cur->rightptr){
                n2=malloc(sizeof(struct tree));
                n2=NULL;
                n2=cur->rightptr;
                enqueue(q,&n2);
            //    printf("%p",&(cur->rightptr));
            }
        
        }
    }
    deletequeue(q);            
    return;
}

valgrind output is :-

==2814== Memcheck, a memory error detector
==2814== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==2814== Using Valgrind-3.10.0.SVN and LibVEX; rerun with -h for copyright info
==2814== Command: ./a.out
==2814==
==2814== Invalid free() / delete / delete[] / realloc()
==2814== at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2814== by 0x4006FB: deletequeue (in /home/ajay/a.out)
==2814== by 0x4008D2: Insertintree (in /home/ajay/a.out)
==2814== by 0x400937: main (in /home/ajay/a.out)
==2814== Address 0x51fd560 is 0 bytes inside a block of size 16 free'd
==2814== at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2814== by 0x4006DE: deletequeue (in /home/ajay/a.out)
==2814== by 0x4008D2: Insertintree (in /home/ajay/a.out)
==2814== by 0x400937: main (in /home/ajay/a.out)
==2814==
In else while==2814==
==2814== HEAP SUMMARY:
==2814== in use at exit: 248 bytes in 12 blocks
==2814== total heap usage: 16 allocs, 5 frees, 312 bytes allocated
==2814==
==2814== 16 bytes in 1 blocks are definitely lost in loss record 1 of 12
==2814== at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2814== by 0x400738: Insertintree (in /home/ajay/a.out)
==2814== by 0x400904: main (in /home/ajay/a.out)
==2814==
==2814== 16 bytes in 1 blocks are definitely lost in loss record 2 of 12
==2814== at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2814== by 0x4005D6: enqueue (in /home/ajay/a.out)
==2814== by 0x4007C5: Insertintree (in /home/ajay/a.out)
==2814== by 0x400915: main (in /home/ajay/a.out)
==2814==
==2814== 16 bytes in 1 blocks are definitely lost in loss record 3 of 12
==2814== at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2814== by 0x4005D6: enqueue (in /home/ajay/a.out)
==2814== by 0x4007C5: Insertintree (in /home/ajay/a.out)
==2814== by 0x400926: main (in /home/ajay/a.out)
==2814==
==2814== 16 bytes in 1 blocks are definitely lost in loss record 4 of 12
==2814== at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2814== by 0x4005D6: enqueue (in /home/ajay/a.out)
==2814== by 0x4007C5: Insertintree (in /home/ajay/a.out)
==2814== by 0x400937: main (in /home/ajay/a.out)
==2814==
==2814== 16 bytes in 1 blocks are definitely lost in loss record 5 of 12
==2814== at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2814== by 0x4005D6: enqueue (in /home/ajay/a.out)
==2814== by 0x400874: Insertintree (in /home/ajay/a.out)
==2814== by 0x400937: main (in /home/ajay/a.out)
==2814==
==2814== 24 bytes in 1 blocks are definitely lost in loss record 9 of 12
==2814== at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2814== by 0x4008E7: main (in /home/ajay/a.out)
==2814==
==2814== 24 bytes in 1 blocks are definitely lost in loss record 10 of 12
==2814== at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2814== by 0x400849: Insertintree (in /home/ajay/a.out)
==2814== by 0x400937: main (in /home/ajay/a.out)
==2814==
==2814== 24 bytes in 1 blocks are definitely lost in loss record 11 of 12
==2814== at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2814== by 0x40088B: Insertintree (in /home/ajay/a.out)
==2814== by 0x400937: main (in /home/ajay/a.out)
==2814==
==2814== 96 (24 direct, 72 indirect) bytes in 1 blocks are definitely lost in loss record 12 of 12
==2814== at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2814== by 0x400722: Insertintree (in /home/ajay/a.out)
==2814== by 0x400904: main (in /home/ajay/a.out)
==2814==
==2814== LEAK SUMMARY:
==2814== definitely lost: 176 bytes in 9 blocks
==2814== indirectly lost: 72 bytes in 3 blocks
==2814== possibly lost: 0 bytes in 0 blocks
==2814== still reachable: 0 bytes in 0 blocks
==2814== suppressed: 0 bytes in 0 blocks
==2814==
==2814== For counts of detected and suppressed errors, rerun with: -v
==2814== ERROR SUMMARY: 10 errors from 10 contexts (suppressed: 0 from 0)

Here i think problem is in allocating memory to n2 . why i do this because i want to store the address of address of left and right pointers of tree and extract that address to get the address of left and right pointers. Is my method correct ? Spend whole yesterday on this problem ? If anyone knows answer please reply.

**anduril462** · 09-08-2014

First things first: providing enough code and sample input for us to compile, run and replicate your problem would be immensely helpful. As it stands, the valgrind output is telling you that you allocate memory in enqueue that is never freed and that you attempt to free memory in dequeue that was never allocated. You did not provide either of those functions, so we can't debug them. Also, why do you think n2 is the problem?

Second: you should compile with the debug flag (-g in GCC). This will allow valgrind to give you more info in the error messages, like line numbers.

You have a logic error. You only consider a memory error when both new and q are NULL. If only one of them fails, your function will attempt to insert a NULL node into the tree.

That's probably not a big deal since, frankly, I'm not sure that you need the list or queue structure in your insert. The only reason to use a queue is if you need to walk back up the tree to modify the tree along the path to the new node (e.g. update height data or rotate branches, etc). It seems you're simply trying to do an iterative (non-recursive) insert so a simple struct tree *temp; with a while loop should be sufficient for traversing the tree. There are two common ways to do this:
1. Use temp to walk the tree and either stop the loop when temp->left or temp->right, depending on whether the data to insert is less or greater than temp's data, is NULL. Then you make temp->left or temp->right point to the new node.
2. Alternatively, you can also declare a struct tree *prev; that points to the node temp pointed to on the prev iteration of the loop. You stop the loop when temp is NULL and insert the new node as the left/right child of prev.

Note, both of those methods require a special case above the while loop to handle inserting the first element, but you already have that in your posted code.

**sparkomemphis** · 09-08-2014

what do you intend to do on line 62 and line 69 ?

Thread: Inserting element in binary tree using pointers

Thread Tools

Search Thread

Display

Inserting element in binary tree using pointers

Similar Threads

Need some help with inserting an element into a tree

Inserting value to a sorted binary tree?

Help with Algorithm for inserting data into Binary Tree

Inserting infix into a binary tree

inserting characters into a binary tree

Tags for this Thread