Problem searching in my Binary Search Tree

Question

Problem is function bin_search. it works steady on function insert. However, it gets frozen on function search. I think if it's fine on insert, it should be fine on search, but it isn't. Here is my code...

"bst.h":

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

typedef struct Node {
    int key;
    void *data;
    struct Node *left, *right;
    void (*destroy)(void *data);
} node;

typedef struct Tree {
    node *head;
    char name;
} tree;

#define key(node) node->key
#define data(node) node->data
#define left(node) node->left
#define right(node) node->right
#define destroy(node) node->destroy
#define tree_head(tree) tree->head

"functions.c":

#include "bst.h"

int bin_search(node *curr, int key, int cnt, node **found) {
    cnt++; printf("cnt+\n");
    
    if (curr == NULL) {
        return -1;
    } else if (curr->key == key) {
        printf("curr_key = key\n"); return cnt;
    }

    if (curr->key < key) {
        printf("curr_key < key\n");
        if (curr->right == NULL) {
            *found = curr;

            return -(cnt + 1);
        }

        return bin_search(curr->right, key, cnt, found);
    } else {
        printf("curr_key > key\n");
        if (curr->left == NULL) {
            *found = curr;
            
            return -(cnt + 1);
        }

        return bin_search(curr->left, key, cnt, found);
    }
}

int insert(tree *root, int key, void *data, void (*destroy)(void *data)) {
    if (root->head == NULL) {
        node* new_node = (node *)malloc(sizeof(node));
        left(new_node) = NULL; right(new_node) = NULL; destroy(new_node) = destroy; key(new_node) = key; data(new_node) = data;
        tree_head(root) = new_node;
        
        printf("created first node\n"); return 1;
    }

    int cnt; node **found;
    if ((cnt = bin_search(root->head, key, 0, found)) < 0) {
        node* new_node = (node *)malloc(sizeof(node));
        left(new_node) = NULL; right(new_node) = NULL; destroy(new_node) = destroy; key(new_node) = key; data(new_node) = data;

        if ((*found)->key < key) {
            (*found)->right = new_node;
        } else {
            (*found)->left = new_node;
        }

        printf("created a node at %d\n", -cnt); return 1;
    } else {
        printf("already exists in tree"); return -1;
    }
}

int search(tree *root, int key, void **data) {
    if (root->head == NULL) {
        printf("tree is empty\n"); return -1;
    }

    int cnt; node **found;
    if ((cnt = bin_search(root->head, key, 0, found)) < 0) {
        return -1;
    } else {
        if ((*found)->key < key) {
            *data = (*found)->right->data;
        } else {
            *data = (*found)->left->data;
        }
        
        return cnt;
    }
}

"main.c":

#include "bst.h"

#define MAX_NUM 8
#define MAX_LEGNTH 200

int main() {
    // create a tree
    tree root; root.head = NULL; root.name = 'a';

    FILE *inpt = fopen("list.txt", "r"); char buffer[MAX_LEGNTH];

    int count = 0;
    while (fgets(buffer, MAX_LEGNTH, inpt) != NULL) {
        printf("adding: %d\n", atoi(buffer)); insert(&root, atoi(buffer), buffer, NULL);
        count++;
    }
    fclose(inpt);

    int result; void **found;
    result = search(&root, 2, found); printf("%d\n", result);  // problem in here!!

    return 0;
}

what is the problem with my 'search' function. I can't find it.

Dare I ask, what is malloc(sizeof(void)) supposed to be doing? — WhozCraig
– WhozCraig, Commented Mar 6, 2022 at 12:22
I'm sorry. that is just one of the useless trying i did, to fix it. i will edit thanks — LIFE1UP
– LIFE1UP, Commented Mar 6, 2022 at 12:23

WhozCraig · Accepted Answer · 2022-03-06 12:32:41Z

1

Besides the utterly non-standard use of sizeof(void), you are not providing a correct out-parameter to search. The point of the found argument is to receive the node pointer if the prospect key was discovered. This...

int cnt; 
node **found; // <== LOOK HERE
if ((cnt = bin_search(root->head, key, 0, found)) < 0) {

is not the way to do that. It should be done like this:


int cnt; 
node *found = NULL;
if ((cnt = bin_search(root->head, key, 0, &found)) < 0) {
//                                        ^^^^^^

and all references to found thereafter should be through found->, not (*found)->

This mistake is made in three different places in your code. The last one is semi-broken, but still broken nonetheless.

void **found = (void *)malloc(sizeof(void));
int result = search(&root, 2, found); 
printf("%d\n", result);

That should use this:

void *found = NULL;
int result = search(&root, 2, &found); 
printf("%d\n", result);

Whether the rest of your code is broken I cannot say, and frankly we're not in the business of being an online-debugger. Use your local debugger tools; that's what they're for. But the items listed above are definitely a problem.

answered Mar 6, 2022 at 12:32

WhozCraig

66.5k11 gold badges82 silver badges148 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

LIFE1UP Over a year ago

thanks for great tip. i've been wrong about double pointer a lot. Anyway, i guess that myself should debugg this code somehow

LIFE1UP Over a year ago

i finally fixed. problem was difference between atoi(input: 1) and atoi(1). somehow my function can't compare them.

Collectives™ on Stack Overflow

Problem searching in my Binary Search Tree

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related