Why am I required to explicitly refer to a property in order to modify it instead of using a reference?

Question

I am brand new to Perl. First time I ever looked at it was a couple days ago and decided to practice implementing some algorithms and data structures to learn. A binary search tree (BST) in this case.

Currently I am using a Node package "Node.pm", a BinarySearchTree package "BST.pm", and an entry point to play around with the code "Main.pl".

My problem arises while inserting the root node of the tree when using a reference to the root property (I know it's just a key => value from hash table, but with conventional OOP terminology I like to refer to it as a property).

Here is the constructor for context:

BST.pm

sub new() {

    my $type = shift;
    my $this = {};
    my $list = shift;

    $this->{'unordered_list'} = $list;
    $this->{'root'} = undef;

    bless($this, $type);
    return $this;
    
}

Constructor takes a list of integers to construct a binary search tree from and the root node is undefined until the first call to "Insert".

In the call to "BuildUnbalancedTree" I am passing a reference to the 'root' property:

Main.pl

$bst = BST->new($nums);

$bst->BuildUnbalancedTree(\$bst->{'root'});

$bst->TraverseInOrder($bst->{'root'});

BST.pm

sub BuildUnbalancedTree(){

    my $this = shift;
    my $root = shift;

    foreach my $key (@{$this->{'unordered_list'}}){

        my $newnode = $this->NewNode($key);
        $this->Insert($$root, $newnode);

    }

}

In the "Insert" method, if I try to insert the root node using the variable passed to it, the tree is partially built except for the root node. The child nodes are all set, but the value of the root node itself is never set.

Here is the method that I expect to work but does not:

sub Insert(){

    my $this = shift;
    my $root = shift;
    my $node = shift;

    if(!$root) {
        
        $root = $node;

    } elsif($node->{'value'} > $root->{'value'}) {

        if(!$root->{'right'}) {
            $root->{'right'} = $node;
        } else {
            $this->Insert($root->{'right'}, $node);
        }

    } else {

        if(!$root->{'left'}){
            $root->{'left'} = $node;
        } else {
            $this->Insert($root->{'left'}, $node)
        }

    } 

}

Assuming that the first condition will only ever be true on the first call to "Insert" I changed this line:

$root = $node;

to :

$this->{'root'} = $node;

And it works, but I'd really like to know why the other approach comes up short. I believe it's because I am dereferencing the root argument in the call to "BuildUnbalancedTree" (And if I don't it breaks everything) but would really appreciate confirmation and maybe some brief expert analysis.

user_4990392 · Answer

Your method Insert should take a reference to the root rather than its value. Call it by doing $this->Insert($root, $newnode); rather than $this->Insert($$root, $newnode);, and change every occurrence of $root by $$root in Insert, and replace the recursive calls by $this->Insert(\$$root->{'right'}, $node); (same thing for left).

The issue is that when you do $this->Insert($$root, $newnode);, you pass the value of the root to Insert. At the first call, $root is not defined yet, which means that you pass undef to Insert (which it stores in its local value $root). Doing if (!$root) { $root = node; } thus just sets the value of $root locally.

Note that once you've passed the reference to the root to Insert (instead of the value), you can simplify the Insert method:

sub Insert {
    my ($root, $node) = @_;

    if(!$$root) {
        $$root = $node;
    } elsif($node->{'value'} > $$root->{'value'}) {
        Insert(\$$root->{'right'}, $node);
    } else {
        Insert(\$$root->{'left'}, $node);
    }
}

I've remove $this from the arguments since you never use it. Call this Insert with Insert($root, $newnode); (rather than $this->Insert(...)).

Additional comments:

Doing my $list = shift; is probably a bad idea: if you do for instance:
```
my @list = (12, 5, 6, 19);
my $bst = BST->new(\@list);
push @list, 42;
$bst->BuildUnbalancedTree(\$bst->{'root'});
```
your BST now contains 42, which might be counter-intuitive. A better approach is probably to pass a list (rather than an array ref) to your constructor:
```
sub new {
    my $class   = shift;
    my @content = @_;

    my $this = { unordered_list => \@content };

    return bless($this, $class);
}
```
(note that I've removed $this->{'root'} = undef;: Perl's autovivification automatically creates this when you try to access it).

Your BuildUnbalancedTree method takes the root as argument, which is somewhat surprising, since the root is stored in the tree. I would suggest instead:

sub BuildUnbalancedTree {
    my $this = shift;

    foreach my $key (@{$this->{'unordered_list'}}){
        my $newnode = $this->NewNode($key);
        $this->Insert(\$this->{root}, $newnode);
    }
}

Why am I required to explicitly refer to a property in order to modify it instead of using a reference?

1 Answers