Home > Software design >  Best way to do a traversal on a hierarchy array
Best way to do a traversal on a hierarchy array

Time:07-06

Need suggestion on the best way to do a traversal on my hierarchy array (at this point I think it's a tree)

A snippet of my array is this:

$rows = array(
array(
    'name' => "Main",
    'id' => 1,
    'parent_id' => 0,
    '_children' => array( 
    array(
       'name' => "Two",
       'id' => 2,
        'parent_id' => 1),
     ),
    array(
       'name' => "Three",
       'id' => 3,
       'parent_id' => 1,
       '_children' => array( 
          array(
         'name' => "Four",
         'id' => 4,
         'parent_id' => 3),
     )),
     )
 )
);

So on that snippet, a quick explanation is that 'Main' node is root and it has 2 children "Two" and "Three" then "Three" has a child namely "Four".

The actual data is based on department and sub-departments so the nodes goes up to 5 layers. The _children field for my layering is because I use Tabulator and that's the required hierarchy on what I want to achieve.

I was able to achieve using recursion the department hierarchy, now I need to traverse each department so I can add employees for each department on the same field "_children".

The reason I wasn't able to achieve adding the employees from the start, it's because when I do recursion it overwrites the employee on _children with the departments.

Any suggestion on how I should tackle the traversal?

Edit - Here is my method that I used for hierarchy:

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

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

    return $branch;
}

CodePudding user response:

I'm not too sure how you want to add employees to the array so I've made some assumptions here.

This code will traverse through all elements of an array recursively until it finds an element that matches the parent ID. At this point, it will add the specified item to the _children property of that "parent".

NOTE: this can be simplified if you preferred passing the array by reference. For this example I've set it up so that it doesn't edit the original array (unless of course you overwrite the variable).

function addChild(array $main, array $item, $parent_id) {
    foreach ($main as $key => $element) {
        if ($parent_id === $element["id"]) {
            // create _children element if not exist
            if (!isset($element["_children"])) {
                $element["_children"] = [];
            }

            $element["_children"][] = $item;

            // specify $main[$key] here so that the changes stick
            // outside this foreach loop
            $main[$key] = $element;


            // item added - break the loop
            break;
        }

        // continue to check others if they have children
        if (isset($element["_children"])) {
            $element["_children"] = addChild($element["_children"], $item, $parent_id);

            // specify $main[$key] here so that the changes stick
            // outside this foreach loop
            $main[$key] = $element;
        }
    }

    return $main;
}

$employee = [
    "id"        => 99,
    "name"      => "Test Employee",
    "parent_id" => 4,
];

$new_rows = addChild($rows, $employee, $employee["parent_id"]);

NOTE: this uses a strict comparison for $parent_id === $element["id"] meaning an int won't match a string. You can either convert these values into the same format or change to a non-strict compare ==.

  •  Tags:  
  • php
  • Related