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(@$tree)-1;
	splice @{$tree}, $index + 1, 0, $subNg;
	return 1;
      }
    }
  }
  return 0;
}