Binary Search Tree search function should return a pointer, an object or the key and the value of the found node?

I have the following node struct for a binary search tree

template <typename key_t, typename value_t>
struct node {
                        key_t key;
                        value_t value;
                        node *parent;
                        node *left;
                        node *right;
}

While implementing the search function for that binary search tree I was concerned about the return type of that function.

At first i thought the following function prototype would be ok

node <key_t, value_t> *search(key_t key);

That function prototype would return a pointer which is not desirable even if you get the key and the value member variables because you are then able to change those members breaking the binary search tree balance. So then I came up with the following solution

bool search(key_t key, value_t *value);

With this function prototype, I would pass a variable value by reference from main and update that if the node was found and return true, else i would return false and the value would remain unchanged. Then the user would check the return value to see if the node value is correct.

Can anyone help me with a more elegant solution to this? I was thinking about returning a node object instead of a node pointer but I don't know how ... and if it is possible.