use strict;
use warnings;
my %Entry;
$Entry{-1} = '';
my @list;
my $id;
while(<DATA>){
  chomp;
  last if /OUTPUT/;
  my $entry = $1 if /\b(\w+)$/;
  my $level = () = $_ =~ m[\-]g;
  my $item;
  $Entry{$level} = $entry; #Remember the last entry
  $item->{id} = ++$id;
  $item->{name} = $entry;
  $item->{parent} = $Entry{$level-1};
  $item->{level} = $level;
  push @list,$item;
}
foreach my $item (@list){
  print join "|", map { $item->{$_} } qw(id level name parent);
  print "\n";

}

__DATA__
foo
->bar
-->troz
->narf
__OUTPUT__
1|0|foo|
2|1|bar|foo
3|2|troz|bar
4|1|narf|foo
[download]

that's good and fine if the data came in the sorted tree order, which it doesn't in my situation. :-) think like pulling from a database, where the order is unknown and i'm not allowed to do ORDER BY in my sql.

bageler,
While I really think using Sort::Tree is probably the best option, here is a purely iterative solution. It has the following requirements:
• IDs will always be numerical
• Root level nodes will always have a parent of 0
• Probably a few others
  Read more... (2 kB)
  Cheers - L~R

@list = sort { $a->{level} <=> $b->{level} } @list;
# Print code goes here
[download]

Update: After re-reading your problem I realized the issue is not in the sorting but in the printing, which I conveniently left out. Since a great solution has already been provided below, I will only point to my iterative solution by using a stack.

bageler seems to be looking for something more complicated that that, I'm afraid - that would simply give

foo
->bar
->narf
-->trof
-->etc.
[download]

I don't know if this is possible without recursion...being lazy, I'd personally use a recursive "GetChildren($id)" routine which greps for the parent $id and pushes the returned list onto itself - terribly inefficient (as you'd be grepping the list for every element), but easier to code :)

Cheers,
Ben.

It's fairly trivial, anyway; but you've not said what the difference between id and name is...which is foo,bar,troz,narf in your example, and what is the other?