SQL | HackerRank 이진 트리 노드 유형(Root, Inner, Leaf) 구분하는 쿼리

You are given a table, BST, containing two columns: N and P, where Nrepresents the value of a node in Binary Tree, and P is the parent of N.

Write a query to find the node type of Binary Tree ordered by the value of the node. Output one of the following for each node:

• Root: If node is root node.
• Leaf: If node is leaf node.
• Inner: If node is neither root nor leaf node.

Sample Input

 

Explanation

The Binary Tree below illustrates the sample:

BST라는 이진 트리 테이블이 주어졌을 때, 각 노드가 Root, Inner, 또는 Leaf 중 어떤 유형에 해당하는지를 판별하는 SQL 쿼리를 작성하고, 그 논리를 쉽게 설명드리겠습니다. 

 

BST 테이블에는 다음과 같은 두 개의 컬럼이 존재합니다:

• N: 현재 노드의 값
• P: 해당 노드의 부모 노드 값 (루트 노드의 경우 NULL)

우리는 각 노드를 다음 세 가지 유형 중 하나로 분류하고자 합니다:

• Root: 부모가 없는 노드 (P IS NULL)
• Leaf: 자식이 없는 노드
• Inner: 부모도 있고 자식도 있는 노드

select N, 
    case 
        when p is null then 'Root'
        when n not in (select distinct p from bst where p is not null) then 'Leaf'
        else 'Inner'
    end as nodetype
from bst
order by n;

1. P IS NULL인 경우 → Root: 부모 노드가 없으므로 루트입니다.
2. 현재 노드 N이 다른 노드의 부모(P)가 아닌 경우 → Leaf: 즉, 어떤 노드의 부모로 등장하지 않는다면 자식이 없다는 의미입니다.
3. 그 외의 경우 → Inner: 부모도 있고 자식도 있는 노드입니다.