[hackerrank] Binary Tree Nodes

[hackerrank] Prepare > SQL > Advanced Select > 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.

Sample Input

Sample Output

1 Leaf
2 Inner
3 Leaf
5 Root
6 Leaf
8 Inner
9 Leaf

Explanation

The Binary Tree below illustrates the sample:

 

[MYSQL]

 

 

[ORCALE]

https://yurimyurim.tistory.com/15

계층구조 쿼리의 START WITH 절에서는 루트(부모행)로 사용될 행을 지정합니다.

• Root 노드는 부모 값(P)이 NULL인 행입니다.

CONNECT BY PRIOR 절에 상위계층(부모행)과 하위계층(자식행)의 관계를 규정합니다.

• 자식컬럼(N) = 부모컬럼(P)로 지정하여 부모에서 자식으로(Top Down) 트리를 구성합니다.

LEVEL은 계층구조 쿼리에서 수행결과의 Depth를 표현하는 Pseudocolumn입니다.

• LEVEL 값이 1인 경우를 'Root'로 지정합니다.

CONNECT_BY_ISLEAF는 계층구조 쿼리에서 최하위 레벨(LEAF) 여부를 반환합니다.

• CONNECT_BY_ISLEAF 값이 1인 경우를 'Leaf'로 지정합니다.
• 그 외의 경우 'Inner'로 지정합니다.

SELECT N
     , CASE WHEN LEVEL = 1 THEN 'Root'
            WHEN CONNECT_BY_ISLEAF = 1 THEN 'Leaf'
            ELSE 'Inner' END NODE
  FROM BST
 START WITH P IS NULL
 CONNECT BY PRIOR N = P
 ORDER BY 1
;

 

 

 

---

이진트리만드는 법

오라클에서의 계층형 쿼리는 

START WITH ... CONNECT BY 절로 생성할 수 있으며 

계층형 정보를 표현하기 위한 목적으로 오라클 8부터 지원되었습니다.

https://tiboy.tistory.com/563

https://coding-factory.tistory.com/461

https://goldswan.tistory.com/36

계층형 쿼리 : 부모, 자식 간의 수직관계를 트리 구조 형태로 보여주는 쿼리 START WITH : 트리 구조의 최상위 행을 지정합니다. CONNECT BY : 부모, 자식의 관계를 지정합니다. PRIOR : CONNECT BY 절에 사용되며 PRIOR에 지정된 컬럼이 맞은편 컬럼을 찾아갑니다. CONNECT BY PRIOR 자식 컬럼 = 부모 컬럼 : 부모 → 자식 순방향 전개 CONNECT BY PRIOR 부모 컬럼 = 자식 컬럼 : 자식 → 부모 역방향 전개 ORDER SIBLINGS : 계층형 쿼리에서 정렬을 수행합니다.

SELECT [컬럼]...
FROM [테이블]
WHERE [조건]
START WITH [최상위 조건]
CONNECT BY [NOCYCLE][PRIOR 계층형 구조 조건];