I think this will do what you want. It's not really been tested except in the most trivial way. Memoization is left as an exercise for the reader.

sub tstruct {
  my $t1   = shift;           # get reference to "root" of tree1
  my $t2   = shift;           # get reference to "root" of tree2
  my $safe = shift || FALSE;  # Flag for safe comparison (normalize fi
+rst)

  if($safe == TRUE) {         # If safe comparison should happen
    &tnormalize($t1);         # Normalize Tree1
    &tnormalize($t2);         # Normalize Tree2
  }

  # Exit if one of them is leaf and the other isn't
  return FALSE if(( $t1->is_leaf($t1) && !$t2->is_leaf($t2)) or
                  (!$t1->is_leaf($t1) &&  $t2->is_leaf($t2)));
  # exit if they have different amount of children
  return FALSE if($t1->n_children($t1) != $t2->n_children($t2));

  return TRUE  if($t1->is_leaf($t1));   # if t1 is leaf -> both are: O
+K

  # => HERE BOTH ARE PARENTS WITH SAME AMOUNT OF CHILDREN

  my $nchild = $t1->n_children($t1);
  my @permutes = 0 .. $nchild - 1;

  do {
PERMUTATION:  {
    for my $i (0 .. $nchild - 1) {
      if (!tstruct($t1->nth_child($t1, $i),
                   $t2->nth_child($t2, $permutes[$i]))) {
          next PERMUTATION 
      }
    }

    # if we make it here, all children compared okay, 
    return TRUE;

  }} while (nextperm(\@permutes)); 

  return FALSE;
}
# }}}




# From Algorithm L in Knuth Vol. 4  Sec 7.2.1.2 (not yet published)
sub nextperm {
  my ($arrayref) = @_;
  my $n = @{$arrayref};
  my $j = $n - 2;
  while ($j >= 0 && ${$arrayref}[$j] >=  ${$arrayref}[$j+1]) {
      $j--;
  }
  return 0 if $j < 0;
  my $q = $n - 1;
  while (${$arrayref}[$j] >= ${$arrayref}[$q]) {
   $q--;
  }
    # swap a[q], a[j]
    (${$arrayref}[$q], ${$arrayref}[$j]) 
      = (${$arrayref}[$j], ${$arrayref}[$q]);
    @{$arrayref}[$j+1 .. $n-1] = reverse @{$arrayref}[$j+1 .. $n-1];
    return 1;
}
[download]

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.