Try something like the following. It should run in linear time, and reasonably efficiently. You will of course want to edit it so it's reading in data from your mySQL table (required fields id and parent), but that should be relatively easy. If you're constructing one specific thread from a mySQL query, you'll also need to store the root id with each post record, so you can select the thread you want without having to map all the post dependencies. 
use strict;
use warnings;
use Data::Dumper;

my (%posts, @threads, $id, $parent, $title);

while (<DATA>) {
    chomp; ### It's easy to add more fields here if you want:
    ($id, $parent, $title) = split / /, $_, 3;
    my %post = ('id' => $id, 'title' => $title);
    $posts{$id} = \%post;
    if ($id == $parent) {
        push @threads, \%post;
    }
    else {
        push @{$posts{$parent}{'children'}}, \%post;
    }
}

construct($_) for @threads;

sub construct {
    my $p = $_[0];
    print "$p->{'id'} $p->{'title'}\n";
    construct($_) for @{$p->{'children'}};
}

__DATA__
1 1 Title
2 1 Re: Title
3 1 Re: Title
4 2 Re: Re: Title
5 5 Title 2
6 5 Re: Title 2
7 4 Re: Re: Re: Title

[download]
EDIT: If you want to generate a subtree of a thread, a lineage field isn't necessary, or even that efficient if you have a large number of threads. Just select all posts with a root equal to the root of the subtree, then map those post dependencies (there probably won't be more than a few dozen posts total) and display just the ones dependant on the subtree ID. This saves you the trouble of storing all ancestor IDs for all posts and having to search through them, which can be quite wasteful in terms of disk space and/or processing time.

In reply to Re: Adjancey Tree Confusion by TedPride
in thread Adjacency Tree Confusion by ChrisR

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.