Ok, you know that arguments are passed to subs in the special array @_. It just so happens that the actual elements of @_ are not simply copies of the actual argument values, but are aliases to them. If you were to do this:

$x = 5;
@a = ( $x );
$a[0] = 7;
print $x; # prints 5
[download]

It's different with @_ when it's carrying the arguments of a sub call.

$x = 5;
foo( $x );
print $x;  # prints 7

sub foo {
    $_[0] = 7;
}
[download]

This behavior can be used to create "OUT" parameters; that is, parameters which can alter their arguments.

(Note that the actual argument would have to be writable for this to work. If we called foo( 5 ); with the above code, we'd get a "Modification of a read-only value attempted" error.)

When called for the first time, $root is undef. insert() detects that and creates a brand new initial node. By using $_[0], insert() accesses $root as an alias - and thus assignes the inital node to $root. So, when insert() returns, $root is no longer undef but a reference to the newly created hash.
This is (one) perlish way to realise the concept of call by reference.

Update: Quote from perlsub:

Any arguments passed in show up in the array @_. Therefore, if you called a function with two arguments, those would be stored in $_[0] and $_[1]. The array @_ is a local array, but its elements are aliases for the actual scalar parameters. In particular, if an element $_[0] is updated, the corresponding argument is updated (or an error occurs if it is not updatable). If an argument is an array or hash element which did not exist when the function was called, that element is created only when (and if) it is modified or a reference to it is taken. (Some earlier versions of Perl created the element whether or not the element was assigned to.) Assigning to the whole array @_ removes that aliasing, and does not update any arguments.

if ( $tree->{VALUE} > $value ) { insert( $tree->{LEFT}, $value ) }
elsif ( $tree->{VALUE} < $value ) { insert( $tree->{RIGHT}, $value )
[download]

if ( $tree->{VALUE} > $value ) { insert( $tree->{LEFT}, $value ) }
elsif ( $tree->{VALUE} < $value ) { insert( $tree->{RIGHT}, $value ) 
else { warn "$value duplicated" }
[download]

or, if you want to include the duplicates, change either '>' to '>=', or '<' to '<=':

if ( $tree->{VALUE} >= $value ) { insert( $tree->{LEFT}, $value ) }
elsif ( $tree->{VALUE} < $value ) { insert( $tree->{RIGHT}, $value )
[download]

A few possibilities. Here are two. The first is a minor change to the code:

my $root;

insert( \$root, 5 );
insert( \$root, 3 );

#...

sub insert {
    my ($treeref, $value) = @_;
    my $tree = $$treeref;

    unless ($$treeref) {
        $tree = {};
        #...
        $$treeref = $tree;
    }
#...
[download]

This just makes it explicit that the variable being passed in (by reference) may be modified.

Another possibility is to have a "create tree" function for when the tree doesn't exist yet, and returns the initialised tree, possibly with the first value being required. The insert function would then need to tell if the tree is pristine and not yet populated (if the first value isn't required during create) to determine whether a new node was needed or not. The create-tree function would construct the tree - so we could call it a constructor. And we're basically at OO, all you have to do is bless the return :-)