Recursive Splay Tree

Question

I am trying to implement a recursive splay tree, bottom up. I recurse down to the node I am need to splay up, and I find the parent and grandparent of that node. Then I am able to either zig zag or zig zig depending on the situation just fine. The problem is after this is done, I return the node which has been splayed once to the previous recursive call. The previous recursive call is referenced to the parent of the node, which is now the child of that node. How do I recurse up splaying the node as I go up?

Answer 1

If I recall correctly, you build a left and right tree as you recurse down to the target node. When you find the target, you construct the final left and right trees using the (original) children of the target, attach the resulting trees as the new children of the target, and return the result in tail-recursive fashion (i.e., all the way back up the stack without further modification).