Thanks for directing me in the right direction. The problem was indeed the $i reference. Also I had a mistake in my right statement. The correct algorithm to generate right and left ids for a hierarchical tree should be:

my $root =1;
my $counter = 1;
rebuild_tree($root);

sub rebuild_tree{
my $idy = shift;

my $result= $dbh->prepare("SELECT id FROM terms WHERE parent_id = ?");
my $left = $dbh->prepare("UPDATE terms SET left_id=? WHERE id = ?");
my $right= $dbh->prepare("UPDATE terms SET right_id=? WHERE id = ?");


$left->execute($ctr++,$idy);
$result->execute($idy);
  while (my $i = $result->fetchrow_hashref()) {
  rebuild_tree($i->{id});
  }
$right->execute($ctr++,$idy);

}#end of sub
[download]

The only way I could get it to work is by inserting the prepare handles in the sub.