Как построить дерево из нод и связать их детьми

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

Базовое владение структурами данных и аккуратность в Java: как хранить детей, нужна ли ссылка на родителя, как собрать дерево из плоского списка. Почти всегда следом просят обойти дерево или построить его из записей вида (id, parentId), пришедших из базы.

Как отвечать

Начните с узла и связей:

• класс узла: TreeNode<T> с полями value, List<TreeNode<T>> children = new ArrayList<>() и, если нужно подниматься вверх, parent;
• связывание: метод addChild(child) добавляет ребёнка в список и сразу выставляет child.parent = this, чтобы две ссылки не разъехались. Наружу список отдавайте через Collections.unmodifiableList, иначе инвариант сломают снаружи;
• сборка из плоского списка: два прохода за O(n). Первым создаёте все узлы и кладёте в HashMap<Long, TreeNode> по id, вторым для каждого берёте родителя из мапы и вызываете addChild. Узел с parentId == null становится корнем;
• обход: в глубину рекурсией или стеком на ArrayDeque, в ширину очередью на том же ArrayDeque. Для глубоких деревьев итеративный вариант надёжнее.

Отдельно скажите про проверки при сборке: несколько корней, ссылка на несуществующего родителя, цикл, когда A родитель B, а B родитель A. Их лучше ловить сразу и бросать понятное исключение, чем получить зависание при обходе.

Если дерево бинарное, вместо списка берут поля left и right, а для упорядоченного хранения в JDK уже есть TreeMap на красно-чёрном дереве.

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

Собирают дерево вложенным циклом: для каждого узла ищут родителя перебором всего списка. На десятках тысяч записей это O(n²) и секунды вместо миллисекунд.

Обходят рекурсией дерево глубиной в десятки тысяч уровней и получают StackOverflowError. Про размер стека и итеративный обход стоит сказать заранее.

Вешают Lombok @Data на узел со ссылкой на родителя. Сгенерированные toString, equals и hashCode уходят в бесконечную рекурсию по связке родителя и ребёнка и тоже падают со StackOverflowError.