1
\$\begingroup\$

With the following data in a table,

+----+-----------+-----------+---------+
| id | name      | parent_id | prev_id |
+----+-----------+-----------+---------+
| 1  | Section 1 | NULL      | NULL    |
| 2  | Item 1.1  | 1         | NULL    |
| 3  | Item 1.2  | 1         | 2       |
| 4  | Item 1.3  | 1         | 3       |
| 5  | Section 2 | NULL      | 1       |
| 6  | Item 2.1  | 5         | NULL    |
| 7  | Item 2.2  | 5         | 6       |
| 8  | Item 2.3  | 5         | 7       |
| 9  | Item 1.4  | 1         | 4       |
+----+-----------+-----------+---------+

I have created this data structure:

[
    1: stdClass Object (
        [id] => 1
        [name] => Section 1
        [parent_id] => NULL
        [prev_id] => NULL
        [children] => [
            2: stdClass Object ([id] => 2, [name] => Item 1.1, [parent_id] => 1, [prev_id] => NULL)
            3: stdClass Object ([id] => 3, [name] => Item 1.2, [parent_id] => 1, [prev_id] => 2)
            4: stdClass Object (...)
            9: stdClass Object (...)
        ]
    ),
    5: stdClass Object (
        [id] => 5
        [name] => Section 2
        [parent_id] => NULL
        [prev_id] => 1
        [children] => [
            6: stdClass Object (...)
            7: stdClass Object (...)
            8: stdClass Object (...)
        ]
    )
]

Here is the working code that I wrote:

function build_tree(array $rows)
{
    $accum = array();

    $rec = function ($parentId = null, $prevId = null) use (&$rec, &$accum, $rows) {
        foreach ($rows as $row) {
            if ($row->parent_id == $parentId && $row->prev_id == $prevId) {
                // add child
                if ($row->parent_id) {
                    if (!isset($accum[$row->parent_id]->children)) {
                        $accum[$row->parent_id]->children = array();
                    }
                    $accum[$row->parent_id]->children[$row->id] = $row;
                // add root
                } else {
                    $accum[$row->id] = $row;
                }
                // find children
                $rec($row->id);
                // find next root
                $rec($row->parent_id, $row->id);
            }
        }
    };
    $rec();

    return $accum;
}

// SELECT * FROM table ORDER BY parent_id, prev_id 
$rows = $itemDAO->getItems();
$items = build_tree($rows);

I am terrible at recursion, so any suggestions on how to improve the code would be helpful.

\$\endgroup\$
3
\$\begingroup\$

There are actually a couple of issues with that approach, so we will step through them one by one.


Let's start with with revising what a tree is. A tree is coherent, undirected graph with a single root node and no loops.

Let's compare that with your sample data (and the implementation based on it):

  • There are no loops - Check
  • There is exactly one root node - No, there are two. And the graph isn't coherent either.

So what you have in your database isn't a tree to start with.

Add a new node which is the only root to your graph, and attach all of the previously created root nodes to this new node. This makes it much easier to work with the data.


Now let's have a look at your code. There are a couple of oddities which strike immediately:

Using == for comparisons

You got to be careful with with == in PHP, it's not typesafe. What this specifically means for you, in your case, it that 0 == NULL is actually true, while the typesafe === operator correctly yields false.

This is an important difference for you, since you are using NULL as a special value, but there might also exist an entry with the perfectly valid numerical ID 0.

Having an $accum variable

This is a direct consequence of not having a single root node. Half of your code revolves around deciding whether a node you visited is a root node or not. Specify a root node explicitly prior to entering the recursion, and this problem is void.

Scanning the result set multiple times instead of indexing it

You don't actually need to iterate over the result set over and over again to find the rows you want. Index it once, and you are good to go:

index = []
foreach(rows as row) {
    index[row->id] = row
}

That's one of the benefits of PHP, you have always a hashmap at hand when you need one ;)

Supporting only a single level of nesting

Let's see what happens if we add another generation of children. $items suddenly lists the child with grandchildren as another regular root.

Ups, that did not go as expected, did it?

Not using the return statement in a recursion

This points out that you have a rather weird understanding of recursion. When you do a recursion, your goal is always to to break the problem down into smaller problems, and to return a partial solution.

In this case, respectively for a tree in general, your goal is always to completely construct a single sub-tree, starting at the current node, prior to passing the current tree back to the parent context.

So in short, for traversing a tree, the recursion function looks something like (pseudo code):

TreeObject build_tree(id, index) {
    tree = new TreeObject(index[id]);
    foreach(index as node) {
        if(node->parent == id) {
            tree->children[] = build_tree(node->id, rows);
        }
    }
    return tree;
}

Notice a difference? There is nothing modified by reference. In a recursion, there is no global state, each single recursion step only reads the data.

A strange way to sort children

There is nothing wrong with wanting to define an order on children of a node, but make sure you are aware what it actually means. It's still a tree, so the same construction applies. But in addition, you want to be able to sort the children of a node. Or even better, already have them sorted, e.g. in a linked list.

A linked list just what you constructed with prev_id, except that you got it linked backwards, not forwards. If you really want to use this structure (I will cover alternatives later), do yourself a favor and use next_id instead. This at allows to traverse the list of children in a more natural way.

Furthermore, if you want to be able to use the linked list half way efficient, make sure that you always store an entry point to the linked list. This means in addition to next_id, also store a first_child on the parent node.

Let's just extend the code sample for better comprehension:

TreeObject build_tree(id, index) {
    tree = new TreeObject(index[id]);

    next_child = tree->first_child;
    while(next_child_id != NULL) {
        tree->children[] = build_tree(next_child, index);
        next_child = index[next_child]->next;
    }
    return tree;
}

Still rather comprehensible, isn't it? Unfortunately, the drawback of using next and first_child references is that updating the database just got slightly more complicated.

It's generally better to just use a index which can be sorted by. So best drop next_id and first_child again, and instead just add an sort_index field which contains a unique number for each entry. You can then just fetch the rows in the correct order from the database, and the previous algorithm already yields the children in the correct order.

(Bonus round: Ensure that sort_index is not only ascending for all children of a single node, but also when traversing the tree in pre-order. Now the previous algorithm can be modified to traverse the result set from the database only a single time, treating it as a queue which only supports the pop and peek functions. If you got that working, congratulations. Your algorithm has just reached O(n) runtime.)


Reinventing the wheel. While it is possible to fix the flaws in the design to get the recursion working properly, storing a tree with a fixed order in a database is actually a standard problem. A problem to which much better solutions than explicitly storing parent-child relations are known.

Before we go ahead, ask yourself a question: Given that the database actually contains a much larger tree, and you only want to fetch a sub-tree starting at a given node, how would you do that?

Right, you couldn't, at least not without modifying the algorithm slightly. You would always have to fetch the whole table content.

There is actually a model which provides that, and also gives the sort order of children for free: Nested set model

Have a read for yourself, knowing how these structures work can never hurt.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Damn, my code sucks :'( but I am very thankful for you giving me some insight. This is hard. I was only writing this code for single level nesting as what is represented in the table. Though, it would be a good idea to try and add more levels. I have some follow-up questions if you don't mind helping me with. If I understood your answer correctly, it would be a good idea to use a sort_index and linked list to represent my data? Little bit confused about sort_index, how would I be able to tell that a given row is a sub-item e.g. Item 2.3 in my data? Would I still keep the parent_id? \$\endgroup\$ – Mikey May 5 '16 at 2:20
  • \$\begingroup\$ Either a linked list, or a sort index, you don't need both, these are entirely different approaches with different characteristiics. If you do it via the linked list, technically you wouldn't need the parent_id, as you can see it's no longer accessed on the algorithm at all. The first_child plus the notion of the next sibling is a sufficient replacement for that. \$\endgroup\$ – Ext3h May 5 '16 at 8:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.