Algorithm for finding the root element
I will make slightly stronger assumptions than that are provided in the question: we have a data structure, representing a tree, that consists of an array of vertices of the tree (allowing random access) and given a vertex, we have access to an array containing that vertex' children (again allowing random access). Furthermore we can check vertices for equality, and given a vertex we can (in $O(1)$ time) locate it in the main array.

On a tree of $n$ nodes, any strategy must take at least $\Omega(n)$ time in the worst case.

Consider a path of $n$ vertices. Define a vertex to be "examined" if it is accessed via the main array, via a children array or is reported as the root. Every non-leaf vertex must be examined by the algorithm: if some non-leaf vertex $v$ is not examined, we can make $v$ the root, making $v$'s child a child of $v$'s predecessor. This is not seen by the algorithm and it will incorrectly report the old root: making $v$ changes its children array (which is not seen by the algorithm as $v$ is not accessed at all) and changes the child array of $v$'s parent (which by the assumption of $v$ not being examined is not seen by the algorithm either).

Thus every non-leaf vertex in a path must be examined and any algorithm thus takes $\Omega(n)$ time.