# Build a tree from a list of paths

*From*: David McCabe <davemccabe@xxxxxxxxx>*Date*: Thu, 21 Jun 2007 05:28:40 -0000

Hi,

I am looking for advice on an algorithm. I have one that's O(n^2), and

I'm hoping that someone here knows of or can think up a faster one.

I am storing hierarchical data in an SQL database, in a format such as

the following (I have heard it called materialied paths, materialized

trees, and enumerated paths):

+----+-------------+

| id | path |

+----+-------------+

| 1 | 1 |

| 2 | 1.2 |

| 3 | 1.3 |

| 4 | 1.3.4 |

+----+-------------+

This corresponds to the tree:

-1

\_2

|_3

\_4

In my program, I wish to be able to access the data using a tree of

objects, where each node includes an array of its children. The

challange is to build such a tree efficiently.

I have an algorithm, but I believe it is O(n^2). So if somebody could

point me to a better algorithm, I would be very much obliged. It is

preferable if the rows do not have to be sorted by path when they come

from the database.

The existing algorithm is this, where $lines is the database results

(all the rows that will end up as part of the tree) and $l is the row

to start from:

function buildTree( $lines, $l ) {

$children = array();

$lpath = preg_quote($l->path);

foreach( $lines as $key => $m ) {

if ( preg_match( "/^{$lpath}\.\d+$/", $m->path ) ) {

// $m->path begins with $l->path; this is a child.

$children[] = buildTree( &$lines, $m );

}

}

$t = new Node($l, $children);

return $t;

}

Thanks much!

--

David McCabe

.

**Follow-Ups**:**Re: Build a tree from a list of paths***From:*Gene

**Re: Build a tree from a list of paths***From:*Pascal Bourguignon

- Prev by Date:
**Re: Another question about big floating point** - Next by Date:
**Re: Build a tree from a list of paths** - Previous by thread:
**Maybe wrong forum. But how come '/0' doesn't show up in the debugger?** - Next by thread:
**Re: Build a tree from a list of paths** - Index(es):