Как обрабатывать структуру данных для генерации HTML-дерева с произвольной глубиной вложенности

Что проверяют

Умеете ли вы работать с рекурсивными структурами и помните ли о безопасности вывода. Следом обычно спрашивают, откуда берутся данные: чаще всего это плоская таблица с parent_id, и тут проверяют, не устроите ли вы N+1 запросов.

Как отвечать

Сначала договоритесь о формате узла. Ключи массива в роли тегов не годятся: два соседних li в одном массиве не поместятся. Удобнее узел вида ['tag' => 'li', 'attrs' => [], 'text' => '', 'children' => []].

Если данные из базы, решение в несколько шагов:

• один запрос: забрать все строки разом, а не спрашивать детей у каждого узла. Для выборки поддерева подойдёт WITH RECURSIVE в MySQL 8 или PostgreSQL;
• сборка дерева за O(n): сгруппировать строки по родителю в $byParent[$row['parent_id']][] = $row, после чего рекурсия берёт детей из этого индекса;
• рендер: рекурсивная функция возвращает строку, для узла это открывающий тег, текст, результат для детей и закрывающий тег;
• экранирование: текст и значения атрибутов через htmlspecialchars($value, ENT_QUOTES | ENT_SUBSTITUTE, 'UTF-8'), имена тегов только из белого списка;
• защита от циклов: если узел по ошибке оказался своим же предком, рекурсия не закончится. Помогает множество посещённых id или ограничение глубины.

На очень глубоких деревьях рекурсию заменяют явным стеком, а с PHP 8.3 переполнение стека выбрасывает обычный Error вместо падения процесса. Если HTML собирается в шаблоне, в Twig то же дерево рисуется рекурсивным макросом.

Где спотыкаются

Вставляют данные в HTML без экранирования. Название категории вида <script>...</script> превращает меню в XSS.

Делают запрос в базу внутри рекурсии. На дереве из тысячи узлов это тысяча запросов, хотя хватило бы одного.

Строят дерево через ссылки &$node в foreach и забывают unset($node) после цикла. Последний элемент потом тихо перезаписывается, и такой баг ищут долго.