PHP - How to build tree structure list?

Question

So, my problem is, that I want to build a tree of these 2 tables:

Parent table:
+-------+---------------+
| pr_id |  parent_name  |
+-------+---------------+
|   1   |       p       |
|   2   |      p_0      | 
|   3   |     p_0_1     | 
|   4   |       q       | 
+-------+---------------+

Child table:
+-------+---------------+---------------------------+
| ch_id |     pr_id     |        child_name         |
+-------+---------------+---------------------------+
|   1   |       1       |            p_0            |
|   2   |       1       |            p_1            |
|   3   |       2       |           p_0_0           |
|   4   |       2       |           p_0_1           |
|   5   |       3       |          p_0_1_0          |
|   6   |       3       |          p_0_1_1          |
|   7   |       4       |            q_0            |
|   8   |       4       |            q_1            |
+-------+---------------+---------------------------+

And the Tree should look like:

• p
  • p_0
    • p_0_0
    • p_0_1
      • p_0_1_0
      • p_0_1_1
• q

Can anybody help me out with a recursive solution??

Answer 1

Multi Loop and/or Recursion are simple but performance wise not the best solution. they are totally fine for smaller datasets but these scale not very well.

a better solution is when every item is only processed one-time.

The Basic Idea is that you create Objects and use the byReference nature of the objects. For that I create "ShadowObjects" that are "glue" everything together, these "ShadowObjects" are later filled with data.

Here an Example

you have a generic id, parentId list

$list = [
    ['id' => 1, 'parent' => 0, 'otherData' => 'a'],
    ['id' => 2, 'parent' => 1, 'otherData' => 'b'],
    ['id' => 3, 'parent' => 1, 'otherData' => 'c'],
    ['id' => 4, 'parent' => 3, 'otherData' => 'd'],
    ['id' => 5, 'parent' => 3, 'otherData' => 'e'],
    ['id' => 6, 'parent' => 4, 'otherData' => 'f'],
    ['id' => 7, 'parent' => 1, 'otherData' => 'g'],
];

The Tree Class

We need an Element that hold and index our Tree-Elements I like to use an TreeClass for that. That class Hold all TreeItems in a list with the unique-ID as identifier, the unique-ID is important to get quick access to every Item.

I also like the getRootItems() method to get all Root_Tree_Elements

class Tree
{
    private array $items = [];
    
    public function getItem(int $id): ?TreeItem
    {
        return $this->items[$id]??null;
    }
    
    public function setItem(TreeItem $item, int $id): void
    {
        $this->items[$id] = $item;
    }
    
    public function getRootItems(): array
    {
        $rootItems = [];
        foreach ($this->items as $item) {
            if ($item->getParent() === null)
                $rootItems[] = $item;
        }
        
        return $rootItems;
    }
}

The Tree Item

is an object that represent a "tree element" it holds the actual data and the parent / children relations

class TreeItem 
{
    private ?TreeItem $parent = null;
    private array $children = [];
    private array $data = [];
    
    public function setParent(?TreeItem $parent): void
    {
        $this->parent = $parent;
    }
    
    public function addChild(TreeItem $child): void
    {
        $this->children[] = $child;
    }
    
    public function setData(array $data): void
    {
        $this->data = $data;
    }
}

Processing Loop

And here is The single Loop that creates the TreeStructure:

from the List we have the information that a parent exists with parent_ID X and that a the item with the ID Y is a child from it.

So the first thing is we ask our Tree if there is an TreeItem with the id X is already existing (only if the ID is not 0 or NULL or something 'invalid'). If not found we create this Tree Item NEW and add this to the Tree, even we don't know all data for the parent, what we know is only the ID of the parent but that is enough as a 'SHADOW_ITEM'.

after that, we look up for the actual TreeItem. We have all Information for that element. We look it up cuz there is the chance that we create it already as a "ShadowItem", So we can fill it with actual DATA. Keep in mind that TreeItem and the Parent are the same type of Objects.

Here again, if the Item not exists create it new and add the new Item to the TreeList. also Add the ParentTreeItem to the current TreeItem.

Then we fill up our Parent Element with the new Children (Bi-Directional Relation parent knows children / child knows Parent).

We don't need to worry about adding the wrong child to the parent or even duplicate, cuz we only process every item only ONE time.

at the end we fill up the actual data to every item. So that in total every ShadowItem contains the real data and loose the state of a ShadowItem.

$tree = new Tree();
foreach($list as $itemData) {
    
    $id = $itemData['id'];
    $pid = $itemData['parent'];
    
    // if ZERO we have root element no parent exists
    
    $parent = $tree->getItem($pid);
    if ($pid > 0 && $parent === null) {
        $parent = new TreeItem();
        $tree->setItem($parent, $pid);
    }
    
    // create new tree item if not exists / otherwise get existing item
    $item = $tree->getItem($id);
    if ($item === null) {
        $item = new TreeItem();
        $item->setParent($parent);
        $tree->setItem($item, $id);
    }
    
    if ($parent !== null) {
        $parent->addChild($item);
    }
    
    $item->setData($itemData);
}

This is an example and "NOT optimize" to make it more easy to understand. there also many things missing on the Tree and the TreeItem to make actual usable,

Feel free to add all methods you like.

for example:

• remove all invalid remaining shadow elements (this can happen if the tree structure data is corrupt, an item points to parent that did not exist anymore)
• or a TreeItem method that give you a ordered array structure of this data and all Children (an __toArray() like).

I use this kind of logic often in Menu generations, it's also easy to "cache"/"store" the finish Tree somewhere. a simple serialize / unserialize do the trick :)

Answer 2

You do not need to create 2 tables in the database for this you can maintain it like below from one table only

+-------+---------------+---------------------------+
|   id  |   parent_id   |           title           |
+-------+---------------+---------------------------+
|   1   |       0       |   Parent Page             |
|   2   |       1       |   Sub Page                |
|   3   |       2       |   Sub Sub Page            |
|   4   |       0       |   Another Parent Page     |
+-------+---------------+---------------------------+

The array generated will be like

Array
(
    [0] => Array
        (
            [id] => 1
            [parent_id] => 0
            [title] => Parent Page
            [children] => Array
                        (
                            [0] => Array
                                (
                                    [id] => 2
                                    [parent_id] => 1
                                    [title] => Sub Page
                                    [children] => Array
                                                (
                                                    [0] => Array
                                                        (
                                                            [id] => 3
                                                            [parent_id] => 1
                                                            [title] => Sub Sub Page
                                                        )
                                                )
                                )
                        )
        )
    [1] => Array
        (
            [id] => 4
            [parent_id] => 0
            [title] => Another Parent Page
        )
)

You need to use the below recursive function to achieve it

function buildTree(array $elements, $parentId = 0) {
    $branch = array();

    foreach ($elements as $element) {
        if ($element['parent_id'] == $parentId) {
            $children = buildTree($elements, $element['id']);
            if ($children) {
                $element['children'] = $children;
            }
            $branch[] = $element;
        }
    }

    return $branch;
}

$tree = buildTree($rows);

The algorithm is pretty simple:

1. Take the array of all elements and the id of the current parent (initially 0/nothing/null/whatever).
2. Loop through all elements.
3. If the parent_id of an element matches the current parent id you got in 1., the element is a child of the parent. Put it in your list of current children (here: $branch).
4. Call the function recursively with the id of the element you have just identified in 3., i.e. find all children of that element, and add them as children element.
5. Return your list of found children.