recursive tree traversal - How to keep track of th

Question

I'm basically trying to build an html ul/li nested list from a multidimensional array representing a tree structure.

The following code works fine but I want to improve it:

I need a way to keep track of the recursion level so I can apply different classes to different levels, add indenting to the generated output, etc.

function buildTree($tree_array, $display_field, $children_field, $class='', $id='') {

  echo "<ul>\n";

  foreach ($tree_array as $row) {

    echo "<li>\n";
    echo $row[$display_field] . "\n";

    if (isset($row[$children_field])) {

      $this->buildTree($row[$children_field]);
    }
    echo "</li>\n";
  }
  echo "</ul>\n";
} 

The $tree_array looks like this:

Array
(
    [0] => Array
        (
            [category_id] => 1
            [category_name] => calculatoare
            [parent_id] => 0
            [children] => Array
                (
                    [0] => Array
                        (
                            [category_id] => 4
                            [category_name] => placi de baza
                            [parent_id] => 1
                        )

                    [1] => Array
                        (
                            [category_id] => 5
                            [category_name] => carcase
                            [parent_id] => 1
                            [children] => Array
                                (
                                    [0] => Array
                                        (
                                            [category_id] => 6
                                            [category_name] => midi-tower
                                            [parent_id] => 5
                                        )

                                )

                        )

                )

        )

    [1] => Array
        (
            [category_id] => 2
            [category_name] => electronice
            [parent_id] => 0
        )

    [2] => Array
        (
            [category_id] => 3
            [category_name] => carti
            [parent_id] => 0
        )

)

I've tagged this as homework because I'd like to use this as an opportunity to improve on my (poor) understanding of recursion so, I'd appreciate answers that would guide me to the solution rather than provide a complete working example :)

Answer 1

public virtual int GetLevelById(int id)
        {
            int i = GetParentById(id);
            if (i == 0)
                return 1;
            else
                return (1 + GetLevelById(i));
        }

public virtual int GetParentById(int t) { var ret = this._list.FirstOrDefault((f) => f.Id == t); if (ret != null) return ret.ParentId; return -1; }

Answer 2

Quick'n'dirty approach (see "spoiler" block below for the implementation):

Add an additional variable $recursionDepth to your function declaration, make it 0 by default.

On each subsequent recursion, call your function with $recursionDepth + 1.

Since the function variables are only "visible" (scoped) for the respective instance of the function, you'll end up with an indicator of the current iteration depth.

Also, line 12 of your function

$this->buildTree();

doesn't look to me as if it would work – the reason being that you're not passing your variables on to the next instance of buildTree.

It probably should look like this:

$this->buildTree($row[$children_field], $display_field, $children_field, $class, $id)

Here's the changes I'd make to your code to achieve what you want:

function buildTree($tree_array, $display_field, $children_field, $class='', $id='', $recursionDepth = 0, $maxDepth = false)
{
    if ($maxDepth && ($recursionDepth == $maxDepth)) return;

    echo "<ul>\n";

    foreach ($tree_array as $row)
    {
        echo "<li>\n";
        echo $row[$display_field] . "\n";

        if (isset($row[$children_field]))
            $this->buildTree($row[$children_field], $display_field, $children_field, $class, $id, $recursionDepth + 1, $maxDepth);

        echo "</li>\n";
    }
    echo "</ul>\n";
}

Answer 3

You are making your life more difficult than it needs to be. The SPL offers a number of iterators for your convenience. Traversing multidimensional arrays is easy with the RecursiveArrayIterator class. Not only does it allow you to process any level depth arrays but it also will keep track of the depth.

Example

$iterator = new RecursiveIteratorIterator(
    new RecursiveArrayIterator($array)
);

for($iterator; $iterator->valid(); $iterator->next())
{
    printf(
        "Key: %s Value: %s Depth: %s\n",
        $iterator->key(),
        $iterator->current(),
        $iterator->getDepth()
    );
}

Example on codepad

As you can see, there is a method getDepth() which will always tell you the current iteration depth. It's a method of the RecursiveIteratorIterator required to iterate over the children in recursive iterators.

If you need to influence what happens when iteration starts or when children are accessed, have a look at my answer to Multidimensional array iteration which shows a custom RecursiveIteratorIterator that will wrap the values of a multidimensional array into xml elements and indent them by the depth of the current iteration (which should be trivial to adapt to ul/li elements).

Also have a look at the Wikipedia Article about Iterators for a general introduction.