LeetCode SQL — Tree Node: root / inner / leaf через self-LEFT-JOIN

Условие

Таблица Tree(id, p_id) — дерево, где p_id — id родителя. Для корня p_id IS NULL.

Для каждого id верните тип: Root, Inner, Leaf. Сортировка по id.

Структура данных

Tree(id INT, p_id INT NULL)

Решение

Лобовое — три проверки

SELECT
  id,
  CASE
    WHEN p_id IS NULL THEN 'Root'
    WHEN id IN (SELECT DISTINCT p_id FROM Tree WHERE p_id IS NOT NULL) THEN 'Inner'
    ELSE 'Leaf'
  END AS type
FROM Tree
ORDER BY id;

Эффективнее — left self-join за один проход

SELECT
  t.id,
  CASE
    WHEN t.p_id IS NULL THEN 'Root'
    WHEN COUNT(c.id) > 0 THEN 'Inner'
    ELSE 'Leaf'
  END AS type
FROM Tree t
LEFT JOIN Tree c ON c.p_id = t.id
GROUP BY t.id, t.p_id
ORDER BY t.id;

COUNT(c.id) > 0 — у t есть дети → внутренний.

Подводные камни

1. IN (NULL, ...). Если Tree.p_id содержит NULL и забыть WHERE p_id IS NOT NULL в подзапросе — IN вернёт UNKNOWN для всего, и Inner никогда не сработает.
2. Дерево с одним узлом. Если Tree содержит только корень — он Root, не Leaf. CASE проверяет p_id IS NULL первым — норм.
3. Дубли id. В реальных БД primary key защищает, но если данные грязные — GROUP BY всё равно даст один тип на id.

Эталонный ответ

CASE с тремя ветками: NULL → Root, есть дети → Inner, иначе Leaf. Через self-LEFT-JOIN Tree t LEFT JOIN Tree c ON c.p_id = t.id и COUNT(c.id) > 0.