Data Structures, Algorithms, & Applications in Java
Chapter 12, Exercise 63

/** @return root of the tree containing element e
  * perform path splitting */
public int find(int e)
{
   int current = e,  // current node
       p,            // parent of current
       gp;           // grandparent of current

   // see if there are pointers to change
   if (node[current].root)
      // e is the tree root, no path to split
      return current;
   p = node[current].parent;
   if (node[p].root)
      // e is a level 2 node, no path to split
      return p;
   gp = node[p].parent;

   // at least one pointer to change
   // move to the root, splitting the path from e to the root
   while(true)
   {
      node[current].parent = gp;  // path splitting
      if (node[gp].root)
         // no more parent pointers to change
         return gp;

      // move current, p, and gp one level up the tree
      current = p;
      p = gp;
      gp = node[p].parent;
   }
}