In users table I have following data.

id   name    parent_id 
1     A           0
2     B           1
3     C           2
4     D           3
5     E           4
6     F           1

A have four level children. E is also children of A. E is the last, it has not any children. Now I can fetch all the children of any parent like the following code.

function getChildren($Id){
   $cache = [];
   $chList = [];
   $allUser = User::orderBy('parent_id', 'asc')
        ->orderBy('parent_id', 'asc')
        ->get();
   foreach($allUser as $user) {
    $cache [$user->parent_id][] = $user;        
   }
  $children0 = empty($cache [$Id]) ? [] : $cache [$Id];
  #first level child
  foreach($children0 as $child1) {

    $chList[$child1->id] = $child1;

    if(!empty($cache [$child1->id])) {

        #Second level child
        foreach($cache [$child1->id] as $child2) {

            $chList[$child2->id] = $child2;

            if(!empty($cache [$child2->id])) {

                #third level child
                foreach($cache [$child2->id] as $child3) {

                    $chList[$child3->id] = $child3;

                    if(!empty($cache [$child3->id])) {

                        #fourth level child
                        foreach($cache [$child3->id] as $child4) {
                            #can not be parent
                            $chList[$child4->id] = $child4;
                            
                        }
                    }
                }
            }
        }
    }
}

return $chList;
}

I can get the actual result by this code. But for huge data it is time consuming. Can any one help me to reduce time complexity or optimize the code?

CodePudding user response：

you can write a recursive CTE in MySQL, like this DBFIDDLE.

WITH RECURSIVE cte1 AS (
    SELECT id, CAST(name AS CHAR(20)) name, parent_id
    FROM table1
    WHERE name='E'
    
    UNION ALL
    
    SELECT table1.id, CONCAT(cte1.name,table1.name), table1.parent_id
    FROM cte1
    INNER JOIN table1 ON table1.id = cte1.parent_id)
SELECT *
FROM cte1;

output:

Above is a quick example of how it can work, but you can change it let it do what you want it to do.

CodePudding user response：

Build a tree from a root such as parent_id == 0. Then traverse the tree to get all the children.

<?php

$users = [
    (object) [
        "id" => "1",
        "name" => "A",
        "parent_id" => "0"
    ],
    (object) [
        "id" => "2",
        "name" => "B",
        "parent_id" => "1"
    ],
    (object) [
        "id" => "3",
        "name" => "C",
        "parent_id" => "2"
    ],
    (object) [
        "id" => "4",
        "name" => "D",
        "parent_id" => "3"
    ],
    (object) [
        "id" => "5",
        "name" => "E",
        "parent_id" => "4"
    ],
    (object) [
        "id" => "6",
        "name" => "F",
        "parent_id" => "1"
    ]
];

function create_tree(&$list, $parents) {
    $tree = [];
    foreach ($parents as $parent) {
        if (isset($list[$parent->id])) {
            $parent->children = create_tree($list, $list[$parent->id]);
        }
        $tree[] = $parent;
    }
    return $tree;
}

function get_children($roots, $parent_id = null) {
    foreach ($roots as $parent) {
        if ($parent_id != null && $parent->id == $parent_id) {
            if (isset($parent->children)) {
                return get_children($parent->children);
            }
        } else if ($parent_id == null) {
            if (isset($parent->children)) {
                $children = get_children($parent->children);
                if (count($children) > 0) {
                    return array_merge($roots, $children);
                }
            }
            return $roots;
        } else {
            if (isset($parent->children)) {
                $children = get_children($parent->children, $parent_id);
                if (count($children) > 0) {
                    return $children;
                }
            }
        }
    }

    return [];
}

$list = array_reduce($users, function ($carry, $user) {
    $carry[$user->parent_id][] = $user;
    return $carry;
}, []);

// assuming root of tree is parent_id == 0
$root_id = 0;
$tree = create_tree($list, $list[$root_id]);

$parent_id = 4;
$children = get_children($tree, $parent_id);

print_r($children);