The Level-Ancestor problem on Pure Pointer Machines

For a tree T the Level-Ancestor problem is the following: given a node x and an integer depth d, find the ancestor of x in T that is at depth d in T. We formulate this problem precisely for the Pure Pointer Machine model, i.e., pointer machines without arithmetic capabilities. We then provide a solution for the problem in the fully dynamic case that runs in worst-case O(lgn) time per operation. We also prove a matching lower bound of to solve the problem.