#!/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]