Sometimes it helps to consider a problem in isolation - remove the database cruft and focus on what needs to be done to solve the issue. Consider:

use strict;
use warnings;

my %data = (
    1 => {replyTo => 0, title => 'root1'},
    2 => {replyTo => 1, title => 'Re: root1 a'},
    3 => {replyTo => 2, title => 'Re^2: root1 b'},
    4 => {replyTo => 1, title => 'Re: root1 c'},
    5 => {replyTo => 2, title => 'Re^2: root1 d'},
    6 => {replyTo => 0, title => 'root2'},
    7 => {replyTo => 6, title => 'Re: root2'},
    );

my %tree;

push @{$tree{$_->[0]}}, $_->[1] for map {[$data{$_}{replyTo}, $_]} key
+s %data;

printTree (\%data, \%tree, 0);


sub printTree {
    my ($data, $tree, $parent, $indent) = @_;
    
    $indent ||= '';
    for my $reply (sort {$a <=> $b} @{$tree{$parent}}) {
        print "$indent- $data{$reply}{title}\n";
        printTree ($data, $tree, $reply, $indent . '   ')
            if exists $tree{$reply};
    }
}
[download]

Prints:

- root1
   - Re: root1 a
      - Re^2: root1 b
      - Re^2: root1 d
   - Re: root1 c
- root2
   - Re: root2
[download]