Weaknesses (in my mind):

• Walking up the tree and then down again
• Using an array to store the relationships and then looping (posibly repeatedly) over that array to get the tree
• Pathological case: linked list described tail first (you'll walk all the way back and then all the way forward again)
• Pathological case: input discribing 2 disjoint trees (your format is flexible). Your code will likely loop FOREVER. It is an error to enter that, but you should still return.

I think you could do it much more efficiently with a hash. Something to the effect of:

my %nodes = ();
foreach my $tuple (split ',', $s) {
    # shorter spliting
    my ($child, $parent) = split ' ', $tuple;

    # init nodes if not already done
    $nodes{$child} ||= { node => $child, children => []};
    $nodes{$parent} ||= { node => $parent, children => []};

    # insert relationship
    push @{$nodes{$parent}{children}}, \$nodes{$child}
    $nodes{$child}{parent} = $parent;
}
[download]

Then you could walk up the tree to get the root and already have a built tree.

Update: your format is flexible enough to describe any directed graph. It is a reasonable expectation that code manipulating such data should halt for any acyclic input.