Having trouble with Valgrind and implementation of min function for BST

Question

I implemented a bst with four functions, add, inorderPrint, min and max. The min and max are supposed to return the smallest/greatest values in the tree and also remove that node. The tree is allowed to be unbalanced. Below is the implementation of my node struct, add function, min function, as well as the valgrind error.

Valgrind Error below:

==2768== Invalid read of size 8
==2768==    at 0x108C13: removeSmallest (bst.c:43)
==2768==    by 0x108BDC: removeSmallest (bst.c:39)
==2768==    by 0x108945: main (problem2.c:25)
==2768==  Address 0x522d8a8 is 8 bytes inside a block of size 24 free'd
==2768==    at 0x4C30D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2768==    by 0x108C0B: removeSmallest (bst.c:42)
==2768==    by 0x108BDC: removeSmallest (bst.c:39)
==2768==    by 0x108945: main (problem2.c:25)
==2768==  Block was alloc'd at
==2768==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2768==    by 0x108A99: add (bst.c:9)
==2768==    by 0x108B08: add (bst.c:15)
==2768==    by 0x108918: main (problem2.c:21)
==2768==

Line 43 is (*root) = (*root)->right;

Line 39 is return removeSmallest((&(*root)->left));

Line 42 is free(*root);

Line 9 is (*root) = (bst_node *)malloc(sizeof(bst_node));

Line 15 is add(&((*root)->left), word);

This is the node struct in a separate file called bst.h

typedef struct  bst_node {
    char * data;
    struct bst_node * right;
    struct bst_node * left;
} bst_node ;

This is the file for the functions implemented.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "bst.h"


void add ( bst_node ** root, char * word ) {
if ((*root) == NULL) {
    (*root) = (bst_node *)malloc(sizeof(bst_node));
    (*root)->data = word;
    (*root)->left = NULL;
    (*root)->right = NULL;
} else {
    if (strcmp(word, (*root)->data) < 0) {
        add(&((*root)->left), word);
    } else if (strcmp(word, (*root)->data) > 0) {
        add(&((*root)->right), word);
    }
}
}

void inorder ( bst_node * root ) {

if(root == NULL) {
    return;
}
inorder(root->left);
printf("  %s", root->data);
inorder(root->right);
}

char * removeSmallest (  bst_node ** root ){
char * answer;

if (*root == NULL) {
    return NULL;
} else {
    if ((*root)->left != NULL) {
        return removeSmallest((&(*root)->left));
    } else if ((*root)->right != NULL) {
        answer = (*root)->data;
        free(*root);
        (*root) = (*root)->right;
        return answer;

    } else {
        answer = (*root)->data;
        free((*root));
        *root = NULL;
        return answer;
    }
}
}

espkk espkk · Accepted Answer · 2020-02-24T03:35:14

You are trying to use freed pointer:

free(*root); (*root) = (*root)->right;

I think this should be

bst_node * new_root = (*root)->right; free(*root); (*root) = new_root;

Having trouble with Valgrind and implementation of min function for BST

1 Answers