C++ Pointers Point to Old Value?

For debugging purposes you can find a minimal code here: https://onlinegdb.com/8XBkeb_nA

Hi StackOverflow Community, As the moderators suggested here's a clear version of my question.

I have defined node class with the following fields:

public:
    S key;
    T value;
    node<S, T> *right_node = nullptr, *left_node = nullptr, *nearest_right_node = nullptr, *nearest_left_node = nullptr;
    int height;

and AVL tree with the following fields:

public:
    node<S, T> *root = nullptr;
    node<S, T> *minimal_node = nullptr;

Let's suppose we have a tree with the values: 1,2,3,4,5,6

nearest_right_node is a pointer to the next bigger node (if exists), for example for node 3 it's 4 and fore node 6 it's nullptr.

minimal_node is a pointer to the smallest node in the tree, which in my case is 1.

I wrote the following code:

int main()
{
    avl_tree<int, int> *tree = new avl_tree<int, int>();
    tree->insert(6, 17);
    tree->insert(4, 6);
    tree->insert(3, 10);
    tree->insert(1, 7);
    tree->insert(2, 8);
    tree->insert(5, 99);
    cout<<tree->search(3)->nearest_right_node->key <<endl;
    cout<<tree->minimal_node->nearest_right_node->nearest_right_node->nearest_right_node->key<<endl;
    tree->remove(4);
    cout<<tree->search(3)->nearest_right_node->key <<endl;
    cout<<tree->minimal_node->nearest_right_node->nearest_right_node->nearest_right_node->key<<endl;

    return 0;
}

Expected Output:

For first output I expect 4 since 4 is the nearest biggest node to 3, for output 2 4 too (since visiting node 3 directly is the same as going from the minimum to the next and the next again). For third one I expect 5 (As 4 got deleted and no more exists) and for line 3 it's the same as the one before, so expecting 5 too.

But, my output is:

4   
4                                                                                                                                                                     
5                                                                                                                                                                        
3 

Which is really strange as the last two lines should refer to the same exact node since we are talking about pointers. What is causing this problem?

I have noted that before I update nearest_right to node 3 for a moment it was 3 thus I doubt that this 3 comes from an outdated pointer...

Here is how my remove function works:

template<class S, class T>
void avl_tree<S, T>::remove(const S &key) {
    root = internal_remove(root, key);
    update_minimum();

    node<S, T> *tmp1 = nearest_right(root, key);
    node<S, T> *tmp2 = nearest_left(root, key);

    if (tmp1 != nullptr) {//if the removed node wasn't the maximum node 
        tmp1->nearest_left_node = tmp2;//update the left of its right.
    }
    if (tmp2 != nullptr) {//if the removed node wasn't the minimum node 
        tmp2->nearest_right_node = tmp1;//update the right of its left.
    }
}