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;
}

templatetypedef · Accepted Answer · 2011-03-21 04:48:21Z

2

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.

answered Mar 21, 2011 at 4:48

templatetypedef

376k112 gold badges954 silver badges1.1k bronze badges

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

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related