Here is a more robust solution (input doesn't need to be ordered, supports multi-level paths) that produces sorted output.

use strict;
use warnings;


sub set {
    my $p = \shift;
    $p = \( $$p->{$_} ) for @_;
}


sub flatten {
    my $node = shift;
    print(join('|', @_), "\n") if @_;

    return if !$node;
    for (sort keys %$node) {
        flatten($node->{$_}, @_, $_);
    }
}


{
    my $tree;

    while (<DATA>) {
        chomp;
        set($tree, split(/\|/));
    }

    flatten($tree);
}

__DATA__
Valentine's Day
Valentine's Day|Cards
Valentine's Day|Flowers
Valentine's|Candy
Valentine's|Telegrams
[download]

Valentine's
Valentine's|Candy
Valentine's|Telegrams
Valentine's Day
Valentine's Day|Cards
Valentine's Day|Flowers
[download]