Working with pointer to pointer

Question

I have a BinarySearchTree struct:

struct BSTNode {
    int value;
    BSTNode *left = nullptr;
    BSTNode *right = nullptr;
};
struct BST {
    BSTNode *root = nullptr;
};

And some functions to work with this tree:

BSTNode **findPosition(BSTNode *node, int value) {
    if (value < node->value) {
        if (node->left) {
            return findPosition(node->left, value);
        } else {
            return &node->left;
        }
    }
    if (value > node->value) {
        if (node->right) {
            return findPosition(node->right, value);
        } else {
            return &node->right;
        }
    }
    return &node;
}
void remove(BSTNode** position, int value) {
    if ((*position)->left == nullptr && (*position)->right == nullptr) {
        delete (*position);
        *position= nullptr;
    }
}
void remove(BST &bst, int value) {
    BSTNode **position = findPosition(bst.root, value);
    if (*position != nullptr) {
        remove(position,value);
    }
}

void add(BSTNode *node, int value) {
    BSTNode **position = findPosition(node, value);

    BSTNode *newNode = new BSTNode;
    newNode->value = value;

    *position = newNode;
}

void add(BST &bst, int value) {
    if (!bst.root) {
        BSTNode *root = new BSTNode;
        root->value = value;
        bst.root = root;
    } else {
        add(bst.root, value);
    }
}

Adding works fine, but removing elements work strangely (now it should work only for leaf nodes). It just sets the value of the node to zero. I think that the problem is in my use of pointers.

What I am doing wrong?

JSF · Accepted Answer · 2015-10-27 17:03:04Z

Your final case return &node; in FindPosition is wrong. It returns garbage.

If you changed the signature to BSTNode **findPosition(BSTNode *&node, int value)

Then in many uses that would fix the final return. I haven't (or depending on what you have vs. what you posted can't) check all uses to see if that covers every way you use findPosition.

Without changing the signature, you are returning the address of a parameter of the call, which is invalid by the time the returned value could be used. With that signature change, the same return instruction would return the correct address. But that signature change represents a significant change to the contract between findPosition and its callers, so it works only if that change is OK with all callers. Otherwise, you would need a bigger change. No change to just findPosition could work without changing its contract with its callers.

Edit (because of your comment). In that final return instruction you need to return the original address of that pointer. Without the signature change you are returning the address of a copy of the pointer. With the signature change, the syntax of the function still treats node as a pointer, but there is an extra level of indirection hidden inside its semantics. With that extra level of indirection, the original address of that pointer is available (and computed by &node) rather than an address of a copy.

Also (building on the answer by dasblinkenlight) the test for NULL pointer is needed in many places with your version, which is error prone. If you push that test to the top of findPosition it is needed in fewer places and more robust:

BSTNode **findPosition(BSTNode *&node, int value) {
    if ( node )
    {    
        if (value < node->value) {
            return findPosition(node->left, value);
        } 
        if (value > node->value) {
            return findPosition(node->right, value);
        }
    }
    return &node;
}

molbdnilo · Accepted Answer · 2015-10-27 16:44:10Z

1

In findPosition,

return &node;

returns the address of the parameter.
Dereferencing it outside of the function is undefined.

It's unclear why the function returns a pointer's address at all.

You need to rethink your removal strategy; in order to remove a node, you need to modify its parent's child pointer.

answered Oct 27, 2015 at 16:44

molbdnilo

67.1k3 gold badges46 silver badges90 bronze badges

Comments

Sergey Kalinichenko · Accepted Answer · 2015-10-27 16:53:10Z

Your code has undefined behavior:

return &node;

returns the address of your function's parameter, which means that any dereference of findPosition's return value would result in undefined behavior.

You can avoid this problem by making sure that findPosition takes a reference to a pointer instead of a pointer:

BSTNode **findPosition(BSTNode*& node, int value) {
    if (node == nullptr) {
        return &node;
    }
    ... // The rest of the code remains the same
}

Note that although the syntax of return &node remains exactly the same, the behavior is different, because the address of a referenced pointer remains valid after the function exits.

Note: Unless this is a learning exercise in writing C code using C++ syntax, consider refactoring the code to encapsulate BSTNode inside BST, and exposing tree functionality as member functions.

Collectives™ on Stack Overflow

Working with pointer to pointer

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related