I am still getting to grips with it too... but i find Data::TreeDumper very useful,
I am sure a filter could be designed to print your output just as you want it.

Hope this helps

use warnings;
use strict;
use Tree::Simple;
use Data::TreeDumper;

my $tree;

while(<DATA>) {
    chomp;
    my ($child, $parent) = split ":";
    print "parent : $parent child : $child\n";
    ## if it is the first parent we have seen
    if (! defined$tree){
      warn "Creating new \$tree\n";
      $tree = Tree::Simple->new("root")->addChild( 
               Tree::Simple->new("$parent")->addChild( 
                  Tree::Simple->new("$child") 
                ) 
            );

   } else {
      warn "\$tree is already growing so adding to it\n";
      ## the tree is already growing so add the child to the appropria
+te parent
      my @nodes = @{ $tree->getAllChildren() };
    print "nodes: ".scalar@nodes."\n";
      my %names = map{$_->getNodeValue() => $_} @nodes;
      print "".(join "\t", "Node Names : ", keys%names, "\n");
      if (exists $names{$parent}){
         warn "Adding child $child to parent $parent\n";
         $names{$parent}->addChild( 
            Tree::Simple->new("$child") 
         );
      } else {
         ## parent doesn't exist, so add it as a child to the root
         warn "Adding parent $parent and child $child to the root\n";
         $tree->addChild(
            Tree::Simple->new("$parent")->addChild( 
                           Tree::Simple->new("$child") 
                         ) 

         );
      }
   }

$tree->DESTROY();

}

$tree->traverse(sub {
    my ($_tree) = @_;
    print (("\t" x $_tree->getDepth()), $_tree->getNodeValue(), "\n");
});

print DumpTree($tree, "tree", FILTER => \&filter, );

sub filter { 
   ## ripped from the Data::TreeDumper docs
   my $s = shift ; 
   if ('Tree::Simple' eq ref $s) { 
      my $counter = 0 ; 
      return ( 
                  'ARRAY' , $s->{_children} , map{[$counter++, $_->{_n
+ode}]} @{$s->{_children}} # index generation
              ) ; 
   } 
   return ( Data::TreeDumper::DefaultNodesToDisplay($s)  ) ; 
}


__DATA__
apple:fruit
granny smith:apple
rotten granny smith:granny smith
orange:fruit
[download]