What is the complexity status for the Nearest Common Ancestor Problem on Trees in which the leaves are attached to the tree in DFS order ? i.e. Suppose one is visiting a tree T in DFS, and at any time one wants to answers NCA queries as NCA(x,y) for any already visited vertices (x,y).
This can be done in constant time $O(1)$ per NCA query and leaf insertion on RAM machines (Gabow, Tarjan '83, Gabow '90), my question is:
what is currently known concerning this problem on Pointer-Machines ?