I've often seen this for hierarchical data -- like you have flat hash (sql results) for some type of hierarchical data. There's probably a more efficient way of doing this but basically you want to chain the keys together until you hit some base criteria. Here's a first cut attempt (using references because i find it easier):

#!/usr/bin/perl

use strict;
use warnings;

use Data::Dumper;

my $nested_hash = {};
my $flat_hash   = {
  4 => -1,
  2 => 6,
  6 => 4,
  3 => 5,
  5 => -1,
 99 => -1,
};

print Dumper( $flat_hash );

# We need to keep track of what we've all ready chained
my $seen = {};

foreach my $key ( sort keys %$flat_hash ) {
  next if defined( $seen->{$key} );
  add_chain( $flat_hash, $nested_hash, $seen, $key );
}

print Dumper( $nested_hash );

sub add_chain {
  my( $flat_hash, $nested_hash, $seen, $key ) = @_;

  # if we've all ready added this key to the nested hash, ignore it
  return if defined( $seen->{$key} );
  $seen->{$key} = 1;

  my $current_key = $flat_hash->{$key};

  if( $current_key == -1 ) {
    # base case
    $nested_hash->{$key} = $flat_hash->{$key};
  }  else {
    # add next chain
    my $chain            = {};
    $nested_hash->{$key} = $chain;
    add_chain( $flat_hash, $chain, $seen, $current_key );
  }
}
[download]

$VAR1 = {
          '6' => 4,
          '99' => -1,
          '4' => -1,
          '3' => 5,
          '2' => 6,
          '5' => -1
        };
$VAR1 = {
          '99' => -1,
          '3' => {
                   '5' => -1
                 },
          '2' => {
                   '6' => {
                            '4' => -1
                          }
                 }
        };
[download]