my $old = {
  this => {
    is => {
      the => {
        day => {},
        hour => {},
      },
      this => {},
    },
  },
  that => {
    that => {
      is => {
        is => {},
        not => {
          is => {
            not => {},
          },
        },
      },
    },
  },
  those => {
    were => {
      the => {
        days => {},
      },
    },
  },
};

##</code><code>##

sub traverse {
    my $depth   = shift;
    my $t       = shift;
    my $nr_kids = scalar keys %$t;
    if( $nr_kids > 0 ) {
        for my $k( sort keys %$t ) {
            print( ' ' x $depth, "$k\n");
            traverse( $depth + 1, $t->{$k} );
        }
    }
    else {
        # at a leaf node
    }
}
__PRODUCES__
that
 that
  is
   is
   not
    is
     not
this
 is
  the
   day
   hour
  this
those
 were
  the
   days

##</code><code>##

sub traverse {
    my $depth   = shift;
    my $t       = shift;
    my $node    = shift;
    my $nr_kids = scalar keys %$t;
    if( $nr_kids > 0 ) {
        for my $k( sort keys %$t ) {
            my $kid = traverse( $depth + 1, $t->{$k}, "$node $k" );
            print( ' ' x $depth, "node=($node) key=($k) kid=($kid)\n");
        }
    }
    else {
        return $node;
    }
}

##</code><code>##

my $new = {
  'this is' => {
      the => {
        day => {},
        hour => {},
      },
      this => {},
  },
  'that that is' => {
        is => {},
        'not is not' => {},
  },
  'those were the days' => {},
};
__PRODUCES__
that that is
 is
 not is not
this is
 the
  day
  hour
 this
those were the days