Binary Tree Nodes

문제

You are given a table, BST, containing two columns: N and P, where N represents 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.

 

BST라는 테이블이 주어지며, 이 테이블에는 N과 P라는 두 개의 열이 있습니다.
여기서 N은 이진 트리에서 노드의 값을 나타내고, P는 해당 노드의 부모 노드를 나타냅니다.

각 노드에 대해 다음 중 하나를 출력하는 쿼리를 작성하세요.
결과는 노드의 값(N)을 기준으로 오름차순 정렬되어야 합니다:

• Root: 해당 노드가 루트 노드인 경우
• Leaf: 해당 노드가 리프(말단) 노드인 경우
• Inner: 해당 노드가 루트도 리프도 아닌 내부 노드인 경우

SELECT 
    DISTINCT P.N AS Node,
    CASE
        WHEN P.P IS NULL THEN 'Root'
        WHEN C.N IS NULL THEN 'Leaf'
        ELSE 'Inner'                   
    END AS Node_Type
FROM 
    BST P
LEFT JOIN 
    BST C ON P.N = C.P   
LEFT JOIN 
    BST C2 ON C.N = C2.P 
ORDER BY P.N;

 

셀프조인을 써서 문제를 해결했다. 프로그래머스 대장균 문제랑 비슷하다.

<2025.04.19 복습>

SELECT 
        N,
        CASE
        WHEN P IS NULL THEN 'Root'
        WHEN N IN (SELECT DISTINCT P FROM BST WHERE P IS NOT NULL) THEN 'Inner'
        ELSE 'Leaf'
        END AS TEMP
FROM BST C
ORDER BY C.N ASC;

이렇게 다른 쿼리가 나올 수 있다.

클로드의 풀이

제가 이 SQL 쿼리의 작동 방식을 단계별로 설명해 드리겠습니다. 간단한 예시 데이터로 보여드리겠습니다.

예를 들어, 다음과 같은 BST 테이블이 있다고 가정해 보겠습니다:

N (노드값)                                                      P (부모값)

1	NULL
2	1
3	1
4	2
5	2
6	3

이 데이터로 표현된 이진 트리는 다음과 같습니다:

    1 (루트)
   / \
  2   3
 / \   \
4   5   6

이제 WHEN N IN (SELECT DISTINCT P FROM BST WHERE P IS NOT NULL) THEN 'Inner' 구문이 어떻게 작동하는지 단계별로 살펴보겠습니다:

1단계: SELECT DISTINCT P FROM BST WHERE P IS NOT NULL 실행

이 쿼리는 "부모로 사용되는 모든 노드값"을 가져옵니다:

• WHERE P IS NOT NULL: 부모가 있는 행만 선택합니다
• SELECT DISTINCT P: 중복 없이 부모값만 선택합니다

결과:

P
--
1
2
3

 

이 결과는 "다른 노드의 부모가 되는 노드값" 목록입니다. 즉, 자식이 있는 노드들입니다.

2단계: N IN (...) 조건 평가

이제 각 노드의 N값을 위에서 얻은 목록과 비교합니다:

노드 1: N=1이 부모 목록 (1,2,3)에 있나요? 예 → 'Inner' 노드 2: N=2가 부모 목록 (1,2,3)에 있나요? 예 → 'Inner'
노드 3: N=3이 부모 목록 (1,2,3)에 있나요? 예 → 'Inner' 노드 4: N=4가 부모 목록 (1,2,3)에 있나요? 아니오 → 이 조건은 거짓 노드 5: N=5가 부모 목록 (1,2,3)에 있나요? 아니오 → 이 조건은 거짓 노드 6: N=6이 부모 목록 (1,2,3)에 있나요? 아니오 → 이 조건은 거짓

전체 CASE 문 평가

이제 각 노드에 대해 전체 CASE 문을 평가합니다:

노드 1:

• P IS NULL? 예 → 'Root' (첫 번째 조건이 참이므로 여기서 중단)

노드 2, 3:

• P IS NULL? 아니오 (첫 번째 조건 실패)
• N IN (부모 목록)? 예 → 'Inner'

노드 4, 5, 6:

• P IS NULL? 아니오 (첫 번째 조건 실패)
• N IN (부모 목록)? 아니오 (두 번째 조건도 실패)
• ELSE → 'Leaf'

<2025년 4월 29일 복습>

처음 짠 쿼리는 셀프조인을 했는데 안그러는게 좋다. 만약 자식수가 많으면 그만큼 깊이가 깊어진다. 그러면 그만큼 조인을 해야하니 이 상황에서는 맞지않다. 오히려 1차 복습때 한 방식이 효율적이다. 

SELECT 
        N,
        CASE
        WHEN P IS NULL THEN 'Root'
        WHEN N IN (SELECT DISTINCT P FROM BST WHERE P IS NOT NULL) THEN 'Inner'
        ELSE 'Leaf'
        END AS TEMP
FROM BST C
ORDER BY C.N ASC;

이번에도 이런방식으로 풀었고 무난히 맞았다.