#!/usr/bin/perl
use strict;
use warnings;
 
package Node;
 
sub new {
    my $class = shift;
    my $self = {};
    $self->{parent} = undef;
    bless $self, $class;
    return $self;
}
 
sub parent {
    my $self = shift;
    if ( @_ ) {
        $self->{parent} = shift;
    }
    return $self;
}
 
package main;
use Data::Dumper;
my ( $child, $parent ) = ( new Node, new Node );
$child->parent($parent);
print Dumper($parent);
print Dumper($child);

__END__

perl rvosa.pl
$VAR1 = bless( {
                 'parent' => undef
               }, 'Node' );
$VAR1 = bless( {
                 'parent' => bless( {
                                      'parent' => undef
                                    }, 'Node' )
               }, 'Node' );

##</code><code>##

sub new {
    my $class = shift;
    my $self = {};
    my $self->{parent} = undef; # <<< you "my" $self twice!
    bless $self, $class;
    return $self;
}