Specific algorithm to recurse through a tree structure in PHP

Question

In PHP, I have a structure like this:

Array
(
    [0] = Array
    (
        'id' => 1,
        'parent' => 0
    )

    [1] = Array
    (
        'id' => 2,
        'parent' => 1
    )

    [2] = Array
    (
        'id' => 3,
        'parent' => 1
    )

    [3] = Array
    (
        'id' => 4,
        'parent' => 2
    )
)

The id is a unique integer and the parent is a reference to another element's id. If parent is 0, then it has no parent. The tree structure looks like this:

1 -> 2 -> 4
  -> 3

(I hope that is clear!). I have been trying to determine an algorithm that will produce a nested array or similar output that exposes the tree hierarchy so I can work with it; for instance one such output would be: tree = ['1' => ['2' => ['4'], '3']]]. The algorithm could support an array of any arbitrary depth; but I am limiting it on the proviso that a child cannot have more than one parent.

Apologies for the non-standard syntax, I hope it effectively communicates what I'm trying to achieve, which is a depth-first search, I think - however the implementations I've come across are too dry for my understand so I'd appreciate some help with this.

possible duplicate of [How can I convert a series of parent-child relationships into a hierarchical tree?](http://stackoverflow.com/questions/2915748/how-can-i-convert-a-series-of-parent-child-relationships-into-a-hierarchical-tre) — jeroen, Mar 12 '12 at 22:35

score 1 · Answer 1 · answered Mar 12 '12 at 22:37

1

You'll find it infinitely easier if you use the key as the id.

$tree = array( 
    1 => array( 'parent' => 0 ), 
    2 => array( 'parent' => 1 ),
    3 => array( 'parent' => 1 ), 
    4 => array( 'parent' => 2 ) );

Now you can loop through all the elements simply appending them to their parent.

$newtree = array();
foreach($tree as $leaf) {
    if (!isset($newtree[$leaf['parent']])) $newtree[$leaf['parent']]=array();
    $newtree[$leaf['parent']][]=$leaf; }
print_r($newtree);

See what you get.

answered Mar 12 '12 at 22:37

DanRedux

9,119
6
23
41

1

*The algorithm could support an array of any arbitrary depth...* Recursion is needed. See: http://stackoverflow.com/questions/2915748/ – webbiedave Mar 12 '12 at 22:43
No, recursion is NOT needed. His pre-existing list is 2 levels.. A list of nodes. Converting from that to a tree is easy. – DanRedux Mar 12 '12 at 22:59
@DanRedux His pre-existing list has 3 levels, `tree = ['1' => ['2' => ['4'], '3']]]` – jeroen Mar 12 '12 at 23:36
That's not his pre-existing list. The thing he has is at the top. The result should be an array tree, but the input is just a list of items that can reference other items. It's not a real tree, just a list, so no recursion is required at all. – DanRedux Mar 12 '12 at 23:47

Specific algorithm to recurse through a tree structure in PHP

1 Answers1