Is it possible to optimize recursion?

Question

PHP

Hello, I'm starting to learn recursion, I wrote a code to display multi-level categories

class Category
{

  public array $tree = [];

  // Построение дерева
  public function createTree($data)
  {
    //Ищем элементы без родительских
    foreach ($data as $item) {
        if ($item['parent_id'] === null) {
          $this->tree[$item['id']] = $item;
          $this->createElemTree($data, $this->tree[$item['id']], $item['id']);
        }
    }

    return $this->tree;
  }

  // Добавление элементов как дочерних
  public function createElemTree($data, &$parentElem, $parentId = null)
  {
    foreach ($data as $key=>$item) {
        if ($item['parent_id'] === $parentId) {
          $parentElem['children'][$key] = $item;
          $this->createElemTree($data, $parentElem['children'][$key], $item['id']);
        }
    }
  }
}


$data = [
    ['id' => 0, 'name' => 'Электроника', 'parent_id' => null],
    ['id' => 1, 'name' => 'Косметика', 'parent_id' => null],
    ['id' => 2, 'name' => 'Инструменты', 'parent_id' => null],
    ['id' => 3, 'name' => 'Телефоны', 'parent_id' => 0],
    ['id' => 4, 'name' => 'Духи', 'parent_id' => 1],
    ['id' => 5, 'name' => 'Samsung', 'parent_id' => 3]
];

$category = new Category();
$tree = $category->createTree($data);

Interested in such a question - is it possible to somehow optimize the current code?

Answer 1

This is trivially done in linear time and without recursion.
First, we create a dict dictionary (id => tree node), in your case, such a dictionary can be the original array, if id goes in order from zero, and $data[id] always contains an element with that id, and the array elements will become tree nodes.
Then we go around the array again and add $item to the children dict[$item['parent_id']] .