This is quite a confusing, but interesting question. The idea is to build a second structure @tree that is a restructured version of @arr. @arr is assumed to be left as is?

The problem is that you are working with references to arrays, your are not copying the underlying arrays when you build @tree. So your line splice @{tree} ... is really inserting parts of @arr into the new variable and operate on them. If you replace this line by creating a copy of @$subNg and insert it into tree you should be fine (hopefully).

As a minor comment: I prefer to use Dumper \@arr as this creates a single structure and is more readable IMHO.

Proposed changes to leave @arr untouched:

    $tree[0] = $arr[0];
    my @copy = @{$arr[1]};
    $tree[1] = \@copy;

   ...

   
    my ($index) = grep { $tree->[$_] eq $treeElement } 0..scalar(@$tre
+e)-1;
    my @copy = @$subNg;
    splice @{$tree}, $index + 1, 0, \@copy;
[download]

Whether or not this modified code creates the desired @tree I do not know.

My guess is the problem is here where you start building the @tree with a ref to an element of @arr.

When you splice elements into @tree they are actually going into @arr. Try

$tree[1] = [ @{$arr[1]} ];
for (my $i=2; $i < @arr; $i+=2){
  buildTree(\@tree, $arr[$i], [ @{$arr[$i+1]} ]);
}
[download]

Thank you for your post, I have modified code according your suggestions and tried to build entire tree:

#!/usr/bin/perl
use strict;
use warnings;
use Data::Dumper;

my @arr = (
        'ng1',     ['ng1_1','ng1_2', 'ng1_3', 'ng1_4'],
        'ng2',     ['ng2_1','ng2_2', 'ng2_3', 'ng2_4'],
        'ng3',     ['ng3_1','ng3_2', 'ng3_3', 'ng3_4'],
        'ng1_1',   ['ng1_1_1','ng1_1_2', 'ng1_1_3', 'ng1_1_4'],
        'ng1_1_1', ['ng1_1_1_u1', 'ng1_1_1_u2', 'ng1_1_1_u3'],
        'ng2_1',   ['ng2_1_u1', 'ng2_1_u2', 'ng2_1_u3']
);

my @tree;

for (my $j=0; $j < (@arr/2); $j+=2){
  $tree[$j] = $arr[$j];
  $tree[$j+1] = [ @{$arr[$j+1]} ];
  for (my $i=$j+2; $i < @arr; $i+=2){
    buildTree(\@tree, $arr[$i], [ @{$arr[$i+1]} ]);
  }
}

print "\@arr:\n";
print Dumper @arr;
print "\@tree:\n";
print Dumper @tree;


sub buildTree{
  my ($tree, $parNg, $subNg) = @_;
  for my $treeElement (@{$tree}){
    if (ref $treeElement eq "ARRAY"){
      &buildTree($treeElement, $parNg, $subNg);
    }
    else{
      if ($treeElement eq $parNg){
        my ($index) = grep { $tree->[$_] eq $treeElement } 0..scalar(@
+$tree)-1;
        splice @{$tree}, $index + 1, 0, $subNg;
        #print Dumper \@tree;
      }
    }
  }
}
[download]

but the output is still confusing:

$VAR1 = 'ng1';
$VAR2 = [
          'ng1_1',
          [
            'ng1_1_1',
            [
              'ng1_1_1_u1',
              'ng1_1_1_u2',
              'ng1_1_1_u3'
            ],
            'ng1_1_2',
            'ng1_1_3',
            'ng1_1_4'
          ],
          [
            'ng1_1_1',
            $VAR2->[1][1],
            [
              'ng1_1_1_u1',
              'ng1_1_1_u2',
              'ng1_1_1_u3'
            ],
            'ng1_1_2',
            'ng1_1_3',
            'ng1_1_4'
          ],
          [
            'ng1_1_1',
            $VAR2->[1][1],
            $VAR2->[2][2],
            [
              'ng1_1_1_u1',
              'ng1_1_1_u2',
              'ng1_1_1_u3'
            ],
            'ng1_1_2',
            'ng1_1_3',
            'ng1_1_4'
          ],
          'ng1_2',
          'ng1_3',
          'ng1_4'
        ];
$VAR3 = 'ng2';
$VAR4 = [
          'ng2_1',
          [
            'ng2_1_u1',
            'ng2_1_u2',
            'ng2_1_u3'
          ],
          [
            'ng2_1_u1',
            'ng2_1_u2',
            'ng2_1_u3'
          ],
          'ng2_2',
          'ng2_3',
          'ng2_4'
        ];
$VAR5 = 'ng3';
$VAR6 = [
          'ng3_1',
          'ng3_2',
          'ng3_3',
          'ng3_4'
        ];
[download]

Am I still missing something? Thank you very much.

In order to complete your "tree building" I would suggest that you record in your recursion whether (return 1) or not (return 0) you have been able to insert the subtree successfully. If not you add it to the root of the tree. See the following modification of your code, employing poj's far more elegant solution to the reference problem:

use strict;
use warnings;
use Data::Dumper;

my @arr = (
       'ng1',     ['ng1_1','ng1_2', 'ng1_3', 'ng1_4'],
       'ng2',     ['ng2_1','ng2_2', 'ng2_3', 'ng2_4'],
       'ng3',     ['ng3_1','ng3_2', 'ng3_3', 'ng3_4'],
       'ng1_1',   ['ng1_1_1','ng1_1_2', 'ng1_1_3', 'ng1_1_4'],
       'ng1_1_1', ['ng1_1_1_u1', 'ng1_1_1_u2', 'ng1_1_1_u3'],
       'ng2_1',   ['ng2_1_u1', 'ng2_1_u2', 'ng2_1_u3']
      );

my @tree;
for (my $i=0; $i < @arr; $i+=2){
  next if &buildTree(\@tree, $arr[$i], [ @{$arr[$i+1]} ] );
  push @tree, $arr[$i], [ @{$arr[$i+1]} ];
}
print Dumper \@tree;

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

Be aware that this only works when in your initial @arr structure, the higher order nodes appear before the lower order nodes if you understand what I mean. E.g. if n1_1 would appear before n1, you are in trouble.

UPDATE: I would also add a counter $index to the loop in sub buildTree to avoid the grep but that is more a matter of taste I guess.

Thank you, this is elegant solution (a little bit complicated for late night but working :)). How did you mean keeping counter for $index? And also, I am aware that this will work only if @arr is "sorted", I will try to improve algorithm and if I lost then I will ask again :) Thank you.

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]

perl -le '
  use strict;
  use warnings;
  use Data::Dumper;
  my @arr = ("ng1", ["ng1_1", "ng1_2", "ng1_2"]);
  my @tree;
  $tree[0] = $arr[0];
  $tree[1] = $arr[1];
  $tree[1] = '2';
  print Dumper @arr;
'
[download]

$arr[$i+1]
[download]

[ @{$arr[$i+1]} ]
[download]

$aref = [@flinstones];
$aref = \@flinstones;
[download]

I am not going to copy & paste my whole advice here, but it seems strange to me no one has yet recommended hashes over arrays for the tree construction.

The fact is that the problem was not solved on stackoverflow. Yes you presented considerably arguments why hashes and not arrays, but I was also wondering why is my @arr changing and it was not asked. I do not think that cross posting is bad, since there may be another peoples on perlmonks and stackoverflow, and as more answers/ideas/solutions the better.

Crossposting is not bad. Crossposting without mentioning it is crossposting is bad.
لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ