Some days ago I was asked about the problem of finding least common ancestor of two given vertices. Specifically, the task is not to use any preprocessing of the tree, and a single LCA query should be answered in time O(r), where r is the distance between query vertices.
If there are no restrictions on memory usage, then the solution can be seen almost instantly: let's lift up both vertices simultaneously, and mark in two arrays all vertices visited during the first path and during the second path. As soon as we meet a vertex that is visited by both paths — this vertex will be the LCA.
But this solution requires O(n) memory, or, if we use hash-set, O(r) memory.
I started to think, is it possible to solve this problem almost without additional memory, i.e., use O(1) of memory. (Of course, the time complexity should remain the same O(r).)
And it turned out that yes, that's possible. Now I set this nice problem to you. (Possibly this is a known problem? I've never seen it before, though.)
As usual, post your solutions at comments, but hide them under edits, so that one can't read your solution accidentally.
Solution in edit.
How to find a vertex with a bigger depth?
We lift up each vertex until we reach the root and we count how many vertices we passed.
Consider an extreme situation: the tree is a chain with root 1. When asking LCA for vetrex n and vetrex n (certainly their LCA is N...they are the same vetrex), lifting up each vetrex leads to O(n) time complexity because you have to go over the whole chain.
in edit
Yes. It is correct solution.