Basically, you would be counting the $treeElements while iterating over them, so you have the correct $index always at hand. Looks a bit redundant, but I prefer it over grep.

sub buildTree{
  my ($tree, $parNg, $subNg) = @_;
  my $index = 0;
  for my $treeElement (@{$tree}){
    if (ref $treeElement eq "ARRAY"){
      return 1 if &buildTree($treeElement, $parNg, $subNg);
    } else {
      if ($treeElement eq $parNg){
    splice @{$tree}, $index + 1, 0, $subNg;
    return 1;
      }
    }
    $index++;
  }
  return 0;
}
[download]