Degrees of categoricity and treeable degrees

We give a characterization of the strong degrees of categoricity of computable structures greater or equal to ${\mathbf{0}}^{\mathrm{\prime }\mathrm{\prime }}$. They are precisely the \emph{treeable} degrees – the least degrees of paths through computable trees – that compute ${\mathbf{0}}^{\mathrm{\prime }\mathrm{\prime }}$. As a corollary, we obtain several new examples of degrees of categoricity. Among them we show that every degree $\mathbf{d}$ with ${\mathbf{0}}^{(\alpha )}\le \mathbf{d}\le {\mathbf{0}}^{(\alpha +1)}$ for $\alpha$ a computable ordinal greater than $2$ is the strong degree of categoricity of a rigid structure. Using quite different techniques we show that every degree $\mathbf{d}$ with ${\mathbf{0}}^{\mathrm{\prime }}\le \mathbf{d}\le {\mathbf{0}}^{\mathrm{\prime }\mathrm{\prime }}$ is the strong degree of categoricity of a structure. Together with the above example this answers a question of Csima and Ng. To complete the picture we show that there is a degree $\mathbf{d}$ with ${\mathbf{0}}^{\mathrm{\prime }}<\mathbf{d}<{\mathbf{0}}^{\mathrm{\prime }\mathrm{\prime }}$ that is not the degree of categoricity of a rigid structure.