Hello all, so I am doing an assignment that requires me to insert new keys into a Red-Black tree. During this my professor wants us to also update the "odd subtree root ranks" of each node.

The odd subtree root ranks are the number of odd keys in the subtree to the left.

So each time I insert a new number I need to balance the tree and then find/update the odd subtree ranks.

I have already fixed and checked the code for my insertion and balancing and this is working fine.

The thing I'm stuck on is updating the odd subtree ranks.

So I am providing some code that I have come up with that I hope is not too confusing that seems to work from the testing I have done so far for one node. After *test* is ran, I update odd into the spot I have saved in that node which is the easy part.

So, (if this code is working right), my question is how do I do this for the whole tree and not just one node since I need to update it with each insertion?

I'm confused on this because the only thing I can think of is adding another recursion on top of this which is killing my brain to think of recursion inside of recursion lol.

Any help/ideas would be appreciated. Thanks

Code:

/* h is the head, v is the Key to start with, and odd is a pointer to update until I find the odd rank of that particular node */
Item test(link h, Key v, int *odd){
Key t = key(h->item);
if (h == z)
return NULLitem;
test(h->l, v, odd);
if (t < v && t%2 != 0)
(*odd)++;
test(h->r, v, odd);
}