Get tree by recursion

Question

I have a flat array with each element containing an 'InstitutionId' and a 'ParentInstitutionId'. Each element will only have ONE parent, but may have multiple children. I know it need recursive solution, I am stuck and can't find way out.

Array
(
    [0] => Array
        (
            [InstitutionId] => 17507
            [InstitutionName] => abc
            [ParentInstitutionId] => 60936
        )

    [1] => Array
        (
            [InstitutionId] => 41679
            [InstitutionName] => abc
            [ParentInstitutionId] => 55701
        )

    [2] => Array
        (
            [InstitutionId] => 55701
            [InstitutionName] => abc
            [ParentInstitutionId] => 
        )

    [3] => Array
        (
            [InstitutionId] => 60936
            [InstitutionName] => abc 
            [ParentInstitutionId] => 128629
        )

    [4] => Array
        (
            [InstitutionId] => 71737
            [InstitutionName] => abc
            [ParentInstitutionId] => 17507
        )

)

How can I make this a tree, children and there children should come under one array starting from root.

Answer 1

You can use the hasMany relationship feature to achieve that. Here is one example you can adapt:

1st - Declare your relationship in your model with a significant name of your choosing. Here we say that the Tree model (file that we're currently in) HAS MANY Tree objects (yes, has many itself).

2nd - Declare the recursive tree loading all immediate children.

Tree Model

class Tree extends Model {

    public function tree_immediate_children() {
        return $this->hasMany(Tree::class);
    }

    public function recursive_tree(){
        return $this->tree_immediate_children()->with('recursive_tree');
    }

}

3rd - Eager load the relationship and then filter by absolute parents only. This way you only get the children through the parents.

Returning the Tree with Children

return \App\Tree::with('recursive_tree')->get()->where('tree_id', null);

---

This is the migration I used to achieve the previous code.

Migration

public function up() {
    Schema::create('trees', function (Blueprint $table) {
        $table->increments('id');
        $table->string('name');
        $table->timestamps();
        $table->integer('tree_id')->unsigned()->nullable(true);
        $table->index(['tree_id']);
        $table->foreign('tree_id')->references('id')->on('trees')->onDelete('cascade');
    });
}

public function down() {
    Schema::drop('trees');
}

Result

{
  "trees": [
    {
      "id": 1,
      "name": "Lauriane Denesik",
      "created_at": "2016-07-25 13:55:34",
      "updated_at": "2016-07-25 13:55:34",
      "tree_id": null,
      "recursive_tree": [
        {
          "id": 4,
          "name": "Lea Terry",
          "created_at": "2016-07-25 13:55:39",
          "updated_at": "2016-07-25 13:55:39",
          "tree_id": 1,
          "recursive_tree": []
        },
        {
          "id": 5,
          "name": "Erna Jacobi",
          "created_at": "2016-07-25 13:55:39",
          "updated_at": "2016-07-25 13:55:39",
          "tree_id": 1,
          "recursive_tree": []
        },
        {
          "id": 6,
          "name": "Carmen Ferry",
          "created_at": "2016-07-25 13:55:39",
          "updated_at": "2016-07-25 13:55:39",
          "tree_id": 1,
          "recursive_tree": [
            {
              "id": 10,
              "name": "Alford Yost",
              "created_at": "2016-07-25 13:55:44",
              "updated_at": "2016-07-25 13:55:44",
              "tree_id": 6,
              "recursive_tree": []
            },
            {
              "id": 11,
              "name": "Eusebio Padberg",
              "created_at": "2016-07-25 13:55:44",
              "updated_at": "2016-07-25 13:55:44",
              "tree_id": 6,
              "recursive_tree": []
            },
            {
              "id": 12,
              "name": "Abdullah Wunsch",
              "created_at": "2016-07-25 13:55:44",
              "updated_at": "2016-07-25 13:55:44",
              "tree_id": 6,
              "recursive_tree": []
            }
          ]
        }
      ]
    },
    {
      "id": 2,
      "name": "Cruz Dickens",
      "created_at": "2016-07-25 13:55:34",
      "updated_at": "2016-07-25 13:55:34",
      "tree_id": null,
      "recursive_tree": [
        {
          "id": 7,
          "name": "Mr. Jesus Macejkovic DDS",
          "created_at": "2016-07-25 13:55:42",
          "updated_at": "2016-07-25 13:55:42",
          "tree_id": 2,
          "recursive_tree": []
        },
        {
          "id": 8,
          "name": "Tracy Jacobson PhD",
          "created_at": "2016-07-25 13:55:42",
          "updated_at": "2016-07-25 13:55:42",
          "tree_id": 2,
          "recursive_tree": []
        },
        {
          "id": 9,
          "name": "Prof. Uriel Goldner",
          "created_at": "2016-07-25 13:55:42",
          "updated_at": "2016-07-25 13:55:42",
          "tree_id": 2,
          "recursive_tree": []
        }
      ]
    },
    {
      "id": 3,
      "name": "Sabryna Torp",
      "created_at": "2016-07-25 13:55:34",
      "updated_at": "2016-07-25 13:55:34",
      "tree_id": null,
      "recursive_tree": []
    }
  ]
}

Answer 2

Since your tags include Laravel, I will give you a laravel solution:

    $collection = collect($yourArray)->keyBy('InstitutionId');
    $grouped = $collection->groupBy('ParentInstitutionId')
        ->map(function($children){
            return $children->keyBy('InstitutionId');
        })->all();
    $array = $collection->all();

    foreach ($array as $id => $item ){
        if (isset($grouped[$id]))
            $array[$id]['children'] = $grouped[$id];
    }

    foreach ($array as $id => $item ){
        if ($item['ParentInstitutionId']) {
            $parentId = $item['ParentInstitutionId'];
            $array[$parentId]['children'][$id] = $item;
        }
    }

    $tree = array_shift($array);