CODEWITHSUNDEEP
c++pointersbinary-search-tree
Ilya Kirillov
Ilya Kirillov

Reputation: 29

Working with pointer to pointer

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?

Upvotes: 0

Views: 82

Answers (3)

JSF
JSF

Reputation: 5321

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

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726489

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.

Upvotes: 1

molbdnilo
molbdnilo

Reputation: 66371

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.

Upvotes: 1

Related Questions