SQL Задача про бинарное дерево

Как-то, на просторах бескрайнего, наткнулся на любопытную задачу, которая, к тому же,
довольно просто решается.

Дальнейший текст, будет полезен для начинающих практиков, у кого есть, хоть какая-то база в написании SQL запросов. Для ушлых сеньоров, все что будет сказано ниже, может показаться слишком просто, и так понятно, примитивно и тривиально.

Пару слов о необходимом арсенале.

Для решения задачи, понадобится следующее:

1. Изучить, либо освежить, как используются, в SQL, условные конструкции CASE WHEN THEN;

2. Повторить использование IN в связке с вложенным запросом, а именно, перед ним.

3. Вспомнить, что делает оператор DISTINCT;

4. Ну и не забывать, что когда проверяем значение на NULL, то пишем не '=', '<>', '!=' а IS NULL / IS NOT NULL.

И так, сама задача.

Есть, стало быть, у нас таблица, Tree:

N - Nodes (узловые элементы);
P - Parent (родительские элементы);

• Написать запрос, для определения типа узла (элемента) бинарного дерева.

• Для каждого узла, вывести одно из следующих значений: Leaf / Inner / Root.

• Упорядочить записи по значению узла.

Например:

Если на входе у нас нечто вроде такого:

В этом месте, можно сделать паузу, и скушав твикс, попробовать нарисовать, по приведенной таблице, бинарное дерево.

То, на выходе мы ожидаем получить:

Соответственно:

Leaf - это конечный элемент, который ни для кого более, не является родительским, как элементы, выделенные на рисунке ниже.

Inner - это элемент, который является родительским для одного, или более других элементов, но и у него самого, также есть родитель.

Root - элемент на вершине иерархии, от которого начинается ветвление, но вышестоящих родительских элементов, у него нет.

У тех, кто знаком с программированием, обычно в голове, сразу начинают мелькать алгоритмы прохода по массиву в цикле, но у нас тут SQL, и надо чуть перенастроиться)

Не исключаю, что кому-то, еще в период средне-высшего образования, могли настолько
"привить любовь", к решению вообще любых, и подобных задач, в частности, что от словосочетания "бинарное дерево", глаз начинает дергаться в двух местах. Однако повторюсь, задача простая, и сейчас можно сделать глубокий вдох, и попробовать ее решить, не читая пока то, что ниже.

Spoiler, дальше будет разбираться решение!

Иногда, те, кто уже знаком c некоторыми приемами, имеют тенденцию к усложнению, и могли навскидку подумать, что здесь понадобится какой-нибудь там хитрый JOIN, но нет. Все что нужно, так это уловить логику отличия разновидностей элементов, которая записана в табличной форме.

1. Совсем уж несложно догадаться, что элемент, который является Root-ом, имеет null, в столбце P (Parent).

2. Далее, столбец N (Node), cодержит перечисление всех узловых элементов.
   Те значения столбца N, которые также присутствуют в столбце P (Parent), это промежуточные элементы, или внутренние (Inner), то есть они для кого-то являются Parent (родительскими) элементами, но и над ними также еще есть элементы, родительские по отношению к ним самим.

   Например, [1] -> [2] -> [5]. Элемент [2], является родительским для элеменnа [1], и имеет свой родительский элемент [5].

3. И наконец, все остальные элементы столбца N, которые не Root, и не являются ни для кого родительскими, это листья, или элементы типа Leaf. Элементы этого типа, отсутствуют в столбце P, т.к. не выступают в роли родительских элементов.

Кто уже понял, как решить, написать и выполнить запрос можно здесь (пишите запрос прямо под имеющимся кодом, учтите, что при первом запуске, система может задуматься).

Решение

SELECT N AS Node,
       CASE
           WHEN P IS NULL THEN 'Root'
           WHEN N IN (SELECT DISTINCT P FROM Tree) THEN 'Inner'
           ELSE 'Leaf'
       END AS "Type"
FROM Tree
ORDER BY N ASC;

Ну а кто хочет держать себя в форме, будь то на случай собеса, или SQL нужен для текущих задач, или просто мозги потренить, запрыгиваем в ТГ канал, SQL Решает (рекомендуется кликнуть на хэштег #задача, и планомерно решать все подряд).

А пока всё.

Успехов в развитии!