A few things to consider:

• What if during you query an exception is thrown? Then everything that catches an exception has to take care of cleaning up the global.
• What if you have a more complex operation, and a query might actually do another query on the tree? With a global, your algorithm wouldn't be "re-entrant".

sub range_query {
    my ($node, $from, $to) = @_;
    return () unless $node;
    return range_query ($node -> left,  $from, $to) if $to   < $node -
+> key;
    return range_query ($node -> right, $from, $to) if $from > $node -
+> key;
    return range_query ($node -> left,  $from, $to), $node -> key,
           range_query ($node -> right, $from, $to)
}
[download]

Abigail

• Exactly who you do it now. Instead of using global array, pass array reference to each subroutine that may require this array or modify it in any way. I have done a similar thing in a couple of my scripts. For example,

  my @data;
  
  foo(\@data);
  bar(\@data);
   
  sub foo {
    my $data_aref = @_;
    # read from a file and
    # save temporary data in the data
    # array
  }
  
  sub bar {
    my $data_aref = @_;
  
    # process data array...
  }
  [download]

• Write a separate subroutine which will do just that: 'find one or more nodes in a binary tree'. Declare your array inside that subroutine (local) and use that array in your subsequent calls that do the actual job of searching the tree.

# Under Construction
[download]

This traverses the whole tree, and every time there's a match, pushes the current node to this array.

But I have a feeling I'm breaking some fundamental OO rules, or maybe this is an example of a ghastly global variable?

_________
broquaint

sub find_key_dupes {
  my $binary_tree=shift;
  my $key=shift;
  my $sub;
  my @dupes;
  $sub=sub {
              my $node=shift;
              return unless $node;
              if ($node->{key} lt $key) {
                  $sub->($node->{right});
              } else {
                  push @dupes,$node if $node->{key} eq $key;
                  $sub->($node->{left});
              }
           };
  $sub->($binary_tree);
  return \@dupes;
}
[download]

Oh and I whipped that code out pretty fast, so its untested but you get the idea I hope. (And I hope its correct ;-)

Yves / DeMerphq
---
Writing a good benchmark isnt as easy as it might look.

And here's a perfect situation to take advantage of Sub::Lexical's ability to emulate nested subs ...

use Sub::Lexical;

sub find_key_dupes {
  my $binary_tree=shift;
  my $key=shift;
  my @dupes;

  my sub get_dupes($) {
    my $node=shift;
    return unless $node;
    if ($node->{key} lt $key) {
      get_dupes($node->{right});
    } else {
      push @dupes,$node if $node->{key} eq $key;
      get_dupes($node->{left});
    }
  }

  get_dupes($binary_tree);
  return \@dupes;
}
[download]

Thanks demerphq, I'll be using this as valid example code in future. <simpsons voice="Mr. Burns">ehhhxcellent</simpsons>.
HTH

_________
broquaint

Look at your traversal routine. Does it use a variable that was defined outside itself? No. The referred array was defined elsewhere, but that is besides the point (and exactly the raison d'etre for references). Inside the function, you use a variable that holds a reference; this reference came from the function's parameters. No global here.

An approach you might take to make this slightly cleaner would be to declare the actual tree traversal routine as private, and have a public function that declares an array, passes a reference to it and its parameters to the private function, and then returns the results from that array. But it is a question of circumstances and taste whether this is actually any real improvement.

Makeshifts last the longest.