I like the idea of just storing the next element but IMHO your algorithm can't handle sub-arrays of size >2 and the iterator stops.

my $a = [ 1, [ 2, [ 3, [ 4, 5 ] ] ] ];
my $d = [ 1,  2,  3,  4,  5 ];


print sameFringe( $a, $d )?"Same\n":"Different\n";

__END__
Use of uninitialized value in string ne ...
Different
[download]

update

oops!!! I just realized that the task is restricted to binary trees! =)

(how boring ;)