#!/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 );
  }
}