fringe.pl

use v5.16;
use warnings;

package TreeNode {
    use Moose;

    has [qw(left right)] => (
        is  => 'rw',
        isa => 'TreeNode',
    );

    has value => ( is => 'rw' );
}

package TreeIterator {
    use Moose;

    has tree => (
        is       => 'ro',
        isa      => 'TreeNode',
        required => 1,
    );

    has stack => (
        is      => 'ro',
        isa     => 'ArrayRef[TreeNode]',
        default => sub { [] },
        traits  => ['Array'],
        handles => {
            push => 'push',
            pop  => 'pop',
        },
    );

    sub BUILD {
        my ($self) = @_;
        $self->push( $self->tree );
    }

    sub next {
        my ($self) = @_;
        my $node = $self->pop();

        if ( !$node ) {
            return undef;
        }

        if ( !$node->left && !$node->right ) {
            return $node->value;
        }

        if ( $node->right ) {
            $self->push( $node->right );
        }
        if ( $node->left ) {
            $self->push( $node->left );
        }

        return $self->next();

    }
}

my $tree1 = TreeNode->new(
    left  => TreeNode->new( value => 'a' ),
    right => TreeNode->new(
        left  => TreeNode->new( value => 'b' ),
        right => TreeNode->new( value => 'c' ),
    )
);

my $tree2 = TreeNode->new(
    left => TreeNode->new(
        left  => TreeNode->new( value => 'a' ),
        right => TreeNode->new( value => 'b' ),
    ),
    right => TreeNode->new( value => 'c' ),
);

my $iterator1 = TreeIterator->new( tree => $tree1 );
my $iterator2 = TreeIterator->new( tree => $tree2 );

while (1) {
    my $value1 = $iterator1->next();
    my $value2 = $iterator2->next();
    
    if (!$value1 && !$value2) {
        last;
    }
    
    if (!$value1 || !$value2 || $value1 ne $value2) {
        $value1 //= 'undef';
        $value2 //= 'undef';
        say "Difference: $value1 $value2";
        last;
    }
    
    say "Same: $value1";
}