Prepare > SQL > Advanced Select > Binary Tree Nodes

Binary Tree Nodes | HackerRank

 

문제

---

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.

 

=> 이진 트리에 관한 테이블이 주어졌다. 각 노드 값과 노트의 종류를(Root, Leaf, Inner) 오름차순 순서로 쿼리하라.

크기가 9, 높이가 3인 이진 트리

• 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조
• 5는 6의 왼쪽 자식 노드, 11은 6의 오른쪽 자식 노드, 6은 5와 11의 부모노드

 

 

 

 

코드

---

SELECT N,
CASE
    WHEN P IS NULL THEN 'Root'
    WHEN N IN (SELECT P FROM BST) THEN 'Inner'
    ELSE 'Leaf'
    END
FROM BST
ORDER BY N;

• Root: p가 null이면 됨
• Inner: N 값이 P값에 없으면 => P값들 중 자기 값이 있으면 이너 노드임.
• Leaf: 나머지

 

 

 

 

노트

---

select distinct a.n
     , case when a.p is null then 'Root' 
            when b.p is null then 'Leaf'
            else 'Inner' end
from bst a
     left join bst b 
     on a.n = b.p 
order by a.n

• 구글링 정답임. 탐구해보자
• distinct의 이유?

SELECT A.N, A.P, B.P, C.P
FROM BST AS A LEFT JOIN BST AS B
ON A.P = B.N
LEFT JOIN BST AS C
ON B.P = C.N
ORDER BY A.N;

• 이진트리 평면도? 를 쿼리한 뒤 서브쿼리로 사용할 생각

 

 

두 번째 시도

SELECT N, 
    CASE
        WHEN P IS NULL THEN 'Root'
        WHEN N IN (SELECT P FROM BST) THEN 'Inner'
        ELSE 'Leaf' 
     END
FROM BST
ORDER BY N;

• 똑같음

 

 

왜 안되는지 생각을 해보자

SELECT N, 
    CASE
        WHEN P IS NULL THEN 'Root'
        WHEN N NOT IN (SELECT P FROM BST) THEN 'Leaf'
        ELSE 'Inner'
     END
FROM BST
ORDER BY N;

1 Inner
2 Inner
3 Inner
4 Inner
5 Inner
6 Inner
7 Inner
8 Inner
9 Inner
10 Inner
11 Inner
12 Inner
13 Inner
14 Inner
15 Root

• 생각을 좀 해봤는데 NULL때문 인거 같음
• IN 구문에서 NULL 과의 비교는 항상 UNKNOWN(FALSE) 값을 반환

 

 

 

 

참조

---

 

[SQL] (NOT)EXISTS 와 (NOT)IN 비교하기