substr, and eq (lexical comparison) instead of = (assignment).

if (substr($_, 0, 4) eq "sub ")
[download]

local $_ = $intree->{contents}; will copy the string. Creating an alias would be better.

for ($intree->{contents})
[download]

However, I don't really see the use of $_. You're simply obfuscating your code. Perhaps you could alias the expression to something shorter yet meaninful.

for my $contents ($intree->{contents})
[download]

As for the question, eval EXPR parses and generates an opcode tree from the supplied source code. That's inherently slow.

If the subs already exist, you'd be better off passing a reference to the sub rather than the source of the sub.

if (ref($contents) eq 'CODE') {
   return $contents->(
      evalTree($intree->{left},  $param),
      evalTree($intree->{right}, $param),
   );
}
[download]

You can get a reference to an existing sub as follows:

sub func { ... }
my $ref = \&func;
[download]

Or you can create a reference to an anonymous sub as follows:

my $ref = sub { ... };
[download]