We study the complexity of isomorphism testing for boolean functions that are represented by decision trees or decision lists. Our results are the following:

•

Isomorphism testing of rank 1 decision trees is complete for logspace.

•

For any constant $r\ge 2$, isomorphism testing for rank r decision trees is polynomial-time equivalent to Graph Isomorphism. As a consequence of our reduction, we obtain our main result for decision trees: A $2^{\sqrt{n}{(\log s)}^{O(1)}}$ time algorithm for isomorphism testing of decision trees of size s over n variables.

•

The isomorphism problem for decision lists admits a Schaefer-type trichotomy: depending on the class of base functions, the isomorphism problem is either in $\mathsf{L}$, or polynomial-time equivalent to Graph Isomorphism, or $\mathsf{coNP}$-hard.