my $tree = init_tree(); # not shown here
my $new_tree  = traverse($tree);

sub traverse {
  my $tree = shift;
  if (defined($tree->{left}))
    traverse($tree);
  }
  if (defined($tree->{right}))
    traverse($tree);
  }
  # .. do stuff
  return $tree;
}