Consider the effect of $f(x)=\frac12(x-x^{-1})$ on the residues mod $p$ (plus $\infty$) of a Mersenne prime $p$. You get the following tree (example $p=7$):  

$$
\begin{array}{ccccccc}
4\\
&\searrow\\
&&1\\
&\nearrow&&\searrow\\
5\\
&&&&0&\rightarrow&\infty\\
2\\
&\searrow&&\nearrow\\
&&6\\
&\nearrow\\
3\\
\end{array}
$$
Proving that a binary tree always results is far beyond my abilities. I merely observed it. Can someone prove it?  

*Addendum*: Primes of the form $k\cdot2^p-1$ or $k\cdot2^p+1$ with small $k$ seem to act quite similar tree-ish. 



A property of Mersenne primes
The critical points of $f$ are at $x=\pm i$, so we try a projective
(a.k.a. fractional linear) change of variable that puts these
critical points at $0$ and $\infty$, namely $x = \alpha(y)$ where
$\alpha(Y) = i(Y+1) \, / \, (Y-1)$, $\alpha^{-1}(X) = (X+i) \, / \, (X-i)$,
and find that $f(\alpha(y)) = \alpha(y^2)$.
Therefore $-$ unusually for a degree-2 rational function $-$ 
the iterates of $f$ have a closed form,
$$
f^{(n)}(x) = \alpha^{-1}(\alpha(x)^{2^n}).
$$
Now if $p=2^l-1$ is a Mersenne prime then $i$ generates
a field of $p^2$ elements, call it $F$,
and $(x+i)/(x-i)$ is an element of the norm-$1$ subgroup of
$F^\*$, which is cyclic of order $p+1 = 2^l$. Since $y \mapsto y^2$
is the doubling map on this group, its graph has the binary-tree structure
that you observed.


Likewise if $p = k 2^l - 1$ for $l \geq 2$ and $k$ odd then the graph is
the union of $k$ binary trees, and if $p = k 2^l + 1$ then
there are square roots of $-1$ in ${\bf Z} / p {\bf Z}$,
and the graph is the union of $k$ binary trees together with two
isolated points at those square roots (corresponding to $y = 0,\infty$).


