Question: Let's say I have an input file where each line contains the path from the root (A) to a leaf

```
echo "A\tB\tC\nA\tB\tD\nA\tE" > lines.txt
A   B   C
A   B   D
A   E

```

How can I easily generate the resulting tree?: `(A(B(C,D),E))` 

I'd like to use GNU tools (awk, sed, etc.) because they tend to work better with large files, but an R script would also work. The R input would be:

```
# lines <- lapply(readLines("lines.txt"), strsplit, " +")
lines <- list(list(c("A", "B", "C")), list(c("A", "B", "D")), list(c("A","E")))

```

Answer: 
In Perl:

```
#!/usr/bin/env perl

use strict;

my $t = {};
while (<>) {
    my @a = split;
    my $t1 = $t;
    while (my $a = shift @a) {
        $t1->{$a} = {} if not exists $t1->{$a};
        $t1 = $t1->{$a};
    }
}

print &p($t)."\n";

sub p {
    my ($t) = @_;
    return
    unless keys %$t;

    return '('
        . join(',', map { $_ . p($t->{$_}) } sort keys %$t)
        . ')';
}

```

This script returns:

```
% cat <<EOF | perl l.pl
A   B   C
A   B   D
A   E
EOF
(A(B(C,D),E))

```

Note that this script, due to recursion in p is not at all suited for large datasets. But that can be easily resolved by turning that into a double for loop, like in the first while above.
Okay, so I think I got it:

```
# input
lines <- c(list(c("A", "B", "C")), list(c("A", "B", "D")), list(c("A","E")))

# generate children
generate_children <- function(lines){
    children <- list()
    for (line in lines) {
        for (index in 1:(length(line)-1)){
            parent <- line[index]
            next_child <- line[index + 1]
            if (is.null(children[[parent]])){
                children[[parent]] <- next_child
            } else {
                if (next_child %notin% children[[parent]]){
                    children[[parent]] <- c(children[[parent]], next_child)
                }
            }
        }
    }
    children
}

expand_children <- function(current_parent, children){
    if (current_parent %in% names(children)){
        expanded_children <- sapply(children[[current_parent]], function(current_child){
            expand_children(current_child, children)
        }, USE.NAMES = FALSE)
        output <- setNames(list(expanded_children), current_parent)
    } else {
        output <- current_parent
    }
    output
}

children <- generate_children(lines)
root <- names(children)[1]
tree <- expand_children(root, children)
dput(tree)
# structure(list(A = structure(list(B = c("C", "D"), "E"), .Names = c("B",""))), .Names = "A")

```

Is there a simpler answer?