Как найти корневой элемент?

Есть массив:

$array = [
            0 => [
                "id" => 1,
                "parent" => 0
            ],
            1 => [
                "id" => 2,
                "parent" => 1
            ],
            2 => [
                "id" => 3,
                "parent" => 2
            ],
            3 => [
                "id" => 4,
                "parent" => 2
            ],
            4 =>[
                "id" => 5,
                "parent" => 2
            ],
            5 =>[
                "id" => 6,
                "parent" => 2
            ],
            6 =>[
                "id" => 7,
                "parent" => 1
            ],
            7 =>[
                "id" => 8,
                "parent" => 7
            ],
            8 =>[
                "id" => 9,
                "parent" => 7
            ],
            9 => [
                "id" => 10,
                "parent" => 7
            ],
            10 => [
                "id" => 11,
                "parent" => 7
            ],
            11 => [
                "id" => 12,
                "parent" => 0
            ]
        ];

Своего рода здесь, категория - подкатегория, но вложенность может быть неограниченной. Мне нужно найти корневой элемент для целой ветки. Например для элемента с индексом 3, корневым элементом будет элемент с индексом 0. По факту, передавая функции id абсолютно любой категории, хочу получить один единственный id корневой категории, для все ветки.
Прошу помочь мне с реализацией и объяснением происходящего. Из прочитанного мною, это можно решить как рекурсией так и с помощью while. Но, что вообще делать и как правильно подойди к этому, ума не приложу.

Если можно, опишите пожалуйста, решение этой задачи несколькими путями и попутно растолковав, что и где происходит, ну и какая из реализаций предпочтительнее. Хочу понять как оно работает и устроено.