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.
Why do it the easy way, if you can use Bourne Shell script instead? Note, this is not even Bash, this is plain old Bourne shell, without arrays...

```
#!/bin/sh
#
# A B C
# A B D
# A E
#
# "" vs "A B C"         -> 0->3, ident 0        -> -0+3 -> "(A(B(C"
# "A B C" vs "A B D"    -> 3->3, ident 2        -> -1+1 -> ",D"
# "A B D" vs "A E"      -> 3->2, ident 1        -> -2+1 -> "),E"
# "A E" vs. endc        -> 2->0, ident 0        -> -2+0 -> "))"
#
# Result: (A(B(C,D),E))
#
# Input stream is a path per line, path segments separated with spaces.

process_line () {
    local line2="$@"
    n2=$#
    set -- $line1
    n1=$#

    s=
    if [ $n2 = 0 ]; then                # last line (empty)
        for s1 in $line1; do
            s="$s)"
        done
    else
        sep=
        remainder=false

        for s2 in $line2; do
            if ! $remainder; then
                if [ "$1" != $s2 ]; then
                    remainder=true
                    if [ $# = 0 ]; then # only children
                        sep='('
                    else                # sibling to an existing element
                        sep=,
                        shift
                        for s1 in $@; do
                            s="$s)"
                        done
                    fi
                fi
            fi

            if $remainder; then         # Process remainder as mismatch
                s="$s$sep$s2"
                sep='('
            fi

            shift                       # remove the first element of line1
        done
    fi

    result="$result$s"
}

result=
line1=
(
    cat - \
    | sed -e 's/[[:space:]]\+/ /' \
    | sed -e '/^$/d' \
    | sort -u
    echo ''                             # last line marker
) | while read line2; do
        process_line $line2
        line1="$line2"

        test -n "$line2" \
            || echo $result
    done

```

This produces the correct answer for two different files (`l.sh` is the shell version, `l.pl` the version in Perl):

```
% for i in l l1; do cat $i; ./l.sh < $i; ./l.pl < $i; echo; done
A
A B
A B C D
A B E F
A G H
A G H I
(A(B(C(D),E(F)),G(H(I))))
(A(B(C(D),E(F)),G(H(I))))

A B C
A B D
A E
(A(B(C,D),E))
(A(B(C,D),E))

```

Hoohah!