Member Avatar for b1izzard

Binary search tree for strings. I tried my best to trace out the error but in vain
Need help.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct bstree
 {
   char keyword[25];
   struct bstree *lnode,*rnode;
 }*root;

void insert(struct bstree *new,struct bstree *old)
   {
     if((strcmp(new->keyword,old->keyword))<0 && old->lnode==NULL)
        {
           old->lnode=new;
        }
     else if((strcmp(new->keyword,old->keyword))<0 && old->lnode!=NULL)
        {
           insert(new,old->lnode);
        }
     else if((strcmp(new->keyword,old->keyword))>0 && old->rnode==NULL)
        {
          old->rnode=new;
        }
     else if((strcmp(new->keyword,old->keyword))>0 && old->rnode!=NULL)
         {
           insert(new,old->rnode);      
         }
     else
        {
          printf("\nKeyword already exists");
        }
   }

void inorder_display(struct bstree *temp)
{
  if(temp!=NULL)
     {
       inorder_display(temp->lnode);
       printf("\n%s",temp->keyword);
       inorder_display(temp->rnode);
     }
}

int main()
{
  int choice=0,count=0,i;
  struct bstree *newloc;
  while(choice!=5)
     {
       printf("\n\n---------BINARY SEARCH TREE------------");
       printf("\n1. Insert");
       printf("\n2. Delete");
       printf("\n3. Display");
       printf("\n4. Search");
       printf("\n5. Exit");
       printf("\nEnter the choice : ");
       scanf("%d",&choice);
        switch(choice)    
          {
            case 1:
                   printf("\nEnter the Number of Keywords you want to insert : ");
                   scanf("%d",&count);
                   for(i=0;i<count;i++)
                      {
                        newloc=malloc(sizeof(struct bstree *));
                        printf("\nENter the Keyword : \n");
                        scanf("%s",newloc->keyword);
                        newloc->lnode=newloc->rnode=NULL;
                        if(root==NULL)
                           {
                             root=newloc;
                           }
                       else
                          {
                            insert(newloc,root);
                          }
                     }
                   break;

            case 3:
                   inorder_display(root);
                   break;

            case 5:
                   exit(0);

            default:
                   printf("\nInvalid Input");
         }
    }
  return 0;
}

I am newbie to Valgrind and got the following output when I run the program

>>valgrind --tool=memcheck --leak-check=yes ./key
---------BINARY SEARCH TREE------------
1. Insert
2. Delete
3. Display
4. Search
5. Exit
Enter the choice : 1

Enter the Number of Keywords you want to insert : 2

ENter the Keyword : 
hello
==13171== Invalid write of size 1
==13171==    at 0x4088D98: _IO_vfscanf (in /lib/libc-2.12.1.so)
==13171==    by 0x408E608: __isoc99_scanf (in /lib/libc-2.12.1.so)
==13171==    by 0x804870D: main (in /home/ravi/codehub/c/key)
==13171==  Address 0x419e02c is 0 bytes after a block of size 4 alloc'd
==13171==    at 0x4025CA3: malloc (vg_replace_malloc.c:236)
==13171==    by 0x80486E8: main (in /home/ravi/codehub/c/key)
==13171== 
==13171== Invalid write of size 1
==13171==    at 0x408AC2E: _IO_vfscanf (in /lib/libc-2.12.1.so)
==13171==    by 0x408E608: __isoc99_scanf (in /lib/libc-2.12.1.so)
==13171==    by 0x804870D: main (in /home/ravi/codehub/c/key)
==13171==  Address 0x419e02d is 1 bytes after a block of size 4 alloc'd
==13171==    at 0x4025CA3: malloc (vg_replace_malloc.c:236)
==13171==    by 0x80486E8: main (in /home/ravi/codehub/c/key)
==13171== 
==13171== Invalid write of size 4
==13171==    at 0x8048712: main (in /home/ravi/codehub/c/key)
==13171==  Address 0x419e048 is not stack'd, malloc'd or (recently) free'd
==13171== 
==13171== Invalid read of size 4
==13171==    at 0x804871D: main (in /home/ravi/codehub/c/key)
==13171==  Address 0x419e048 is not stack'd, malloc'd or (recently) free'd
==13171== 
==13171== Invalid write of size 4
==13171==    at 0x8048724: main (in /home/ravi/codehub/c/key)
==13171==  Address 0x419e044 is not stack'd, malloc'd or (recently) free'd
==13171== 

valgrind: m_mallocfree.c:225 (mk_plain_bszB): Assertion 'bszB != 0' failed.
valgrind: This is probably caused by your program erroneously writing past the
end of a heap block and corrupting heap metadata.  If you fix any
invalid writes reported by Memcheck, this assertion failure will
probably go away.  Please try that before reporting this as a bug.

==13171==    at 0x380284FD: report_and_quit (m_libcassert.c:193)
==13171==    by 0x380286C7: vgPlain_assert_fail (m_libcassert.c:267)
==13171==    by 0x380356E3: vgPlain_arena_malloc (m_mallocfree.c:225)
==13171==    by 0x38066347: vgPlain_cli_malloc (replacemalloc_core.c:83)
==13171==    by 0x38002F68: vgMemCheck_new_block (mc_malloc_wrappers.c:200)
==13171==    by 0x380033D6: vgMemCheck_malloc (mc_malloc_wrappers.c:237)
==13171==    by 0x38068CB7: vgPlain_scheduler (scheduler.c:1394)
==13171==    by 0x38096274: run_a_thread_NORETURN (syswrap-linux.c:94)

sched status:
  running_tid=1

Thread 1: status = VgTs_Runnable
==13171==    at 0x4025CA3: malloc (vg_replace_malloc.c:236)
==13171==    by 0x80486E8: main (in /home/ravi/codehub/c/key)

Need a little help in analyzing the above output.

Firstly, on line 68

newloc=malloc(sizeof(struct bstree *));

your allocating memory for the size of a pointer not the size of struct bstree..It should be

newloc=malloc(sizeof(struct bstree));
Member Avatar for b1izzard

@gerard : Thanks:), this solved my problem.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.