Why does this search function return a pointer to a pointer?

Question

#ifndef _BST_H_

/* Returns negative (left<right), zero (left==right), or positive (left>right). */
typedef int comparator(void* left, void* right);

struct bst_node {
    void* data;
    struct bst_node* left;
    struct bst_node* right;
};

struct bst_node* new_node(void* data);
void free_node(struct bst_node* node);
struct bst_node** search(struct bst_node** root, comparator compare, void* data);
void insert(struct bst_node** root, comparator compare, void* data);
void delete(struct bst_node** node);

#endif

This is a header file. I don't understand about search function, why is the return type node**?

Edited: added search func here:

struct bst_node** search(struct bst_node** root, comparator compare, void* data) {
    struct bst_node** node = root;
    while (*node != NULL) {
        int compare_result = compare(data, (*node)->data);
        if (compare_result < 0)
            node = &(*node)->left;
        else if (compare_result > 0)
            node = &(*node)->right;
        else
            break;
    }
    return node;
}

score 2 · Accepted Answer · answered Mar 21 '11 at 04:48

I would guess that the function returns a pointer to a pointer so that your search function can be used to implement insert. If search just returns a pointer to a node and the node isn't found, then you have to walk the tree again to figure out what pointer you need to rewire to do an insertion. If it instead returns a pointer to the node pointer that ended up being null, then insert can be implemented by just reassigning this pointer to point to the new node that needs to be inserted.

Just a guess.

Why does this search function return a pointer to a pointer?

1 Answers1

Linked