Problem while working with pointers and struct in C++

Question

I wrote Cartesian tree for solution for this task.

My full code

And I faced with at first signt very confusing problem.. I have my structure and two functions. I need to pass pointer on my tree, make some actions, and after that I need my original object value before passing it to function calc.

struct item {

    int prior;
    long long key, sum;
    item *l, *r;

    item(long long key, int prior) {
        this->key = key;
        this->sum = key;
        this->prior = prior;
        this->l = nullptr;
        this->r = nullptr;
    }

};

typedef item *pitem;


long long calc(pitem &t, long long l, long long r) {

    pitem first = nullptr, second = nullptr, out = nullptr;
    split(t, l - 1, first, second);
    split(second, r, out, first);

    return sum(out);
}

*additional function split

void split(pitem t, long long key, pitem &l, pitem &r) {
    if (!t) {
        l = r = nullptr;
        return;
    }
    if (key < t->key)
        split(t->l, key, l, t->l), r = t, update_info(r);
    else
        split(t->r, key, t->r, r), l = t, update_info(l);
    update_info(t);
}

At first I tried to pass pointer without "&" in function. It hasn't worked. After that I've tried to create temp-value with the same value and pass pointer on this new object in function, but It doesn't work and even more: my original object at pointer tree also changes at that time.. I used a lot of things, but they didn't work. It's like I try to create temp values and not to change my main object on *t pointer, but it still changes with them. Please hepl me, I've spent may be 4 yours only on this problem and stil don't know that to do ...

Answer 1

The code is not complete and intended behaviour isn't clear, but there are some visible problems. This code

if (!t) {
    l = r = nullptr;
    return;
}

doesn't make sense, t, r and l aren't pointers, they are references. This code shouldn't even compile. Here your code falls into one of rules "how to write unsupported code" by reusing same variable names. It hard to relate to the identifiers of various objects when they are all same.

Expressions r = t and l = t would change actual objects, it assigns an item referred by t to l and vice versa. After one of them both items references by function parameters will be equal to each other. A function parameter passed by reference is an alias of original object.

In function split first parameter is not a reference, so if update_info is intended to change t, it actually wouldn't change anything. Function parameter t here is passed by value and is a local variable initialized with argument's value.