#!/usr/bin/perl

use strict;
use warnings;

my (%child, @ancestor); 

while(<DATA>){
	my ($node, $left, $right);
	$node = $1, $left = $2, $right = $3 if(/(.+?): (.+?), (.+)/);
	$child{$node} = $left . ' ' . $right; 	
	push @ancestor, $node;

	if($left =~ /^\w/ && $right =~ /^\[/){
		my $children_node = child_check($child{$right});
		$child{$node} = $left . ', ' . $children_node;
		# $right wird vom Array @ancestor entfernt
		@ancestor = grep !/^\Q$right\E$/, @ancestor;
	}
}

foreach(@ancestor){
	#my $vater_id = $_;
	my $descendant = $child{$_};
	print "$_:\t$descendant\n";
}

sub child_check{
	my $string = shift;
	my @arr_ance = split(/ /, $string);
	my @all_children;
	foreach my $ance(@arr_ance){
		if (defined $child{$ance}) {
			my @descendants = split(/ /, $child{$ance});
			foreach my $desc(@descendants){
				if (defined $child{$desc}) {
					child_check($child{$desc});
				}
				else{
					push @all_children, $desc;
				}
			}		
		}
		else{
			push @all_children, $string;
		}	
	}	
	my $join_children = join(', ', @all_children);
	return $join_children;
}

__DATA__
[1]: a, b
[2]: c, [1]
[3]: d, e
[4]: f, [3]
[5]: g, h
[6]: i, [5]
[7]: [2], [4]
[8]: j, [6]
[9]: [7], [8]