[Oracle] 해커랭크(HackerRank) 문제 풀이 - 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:

 

<문제 정리>

세 가지 유형으로 나누어서 이진트리 노드의 계층을 출력하면 된다

1.상위 노드가 없는 애 -> 'Root'

2.상위, 하위 모두 존재하는 애 -> 'Inner'

3.하위 노드가 없는 애 -> 'Leaf'

출력시 N(노드)의 값을 기준으로 오름차순으로 정렬하여 출력하면 된다

 

<문제 풀이 1>

SELECT TB1.N 
	 ,CASE WHEN TB1.LE = TB2.MA THEN 'Leaf' 
	    WHEN TB1.LE = TB2.MI THEN 'Root'
	    ELSE 'Inner' END
FROM (SELECT N,LEVEL LE 
	  FROM BST 
      START WITH P IS NULL
      CONNECT BY PRIOR N = P
      ORDER BY N) TB1
,(SELECT MAX(LEVEL) MA ,MIN(LEVEL) MI
	  FROM BST
	  START WITH P IS NULL
	  CONNECT BY PRIOR N = P) TB2;

 

* 오라클 LEVEL 함수

 

SELECT N,P,LPAD(' ', (LEVEL-1)*2) || LEVEL LEV
     FROM BST
     START WITH P IS NULL
     CONNECT BY PRIOR N = P;

<그림1>

 

*START WITH ->  계층형 쿼리의 루트노드(최상위 노드) 설정 (P가 부모 노드이니 부모가 없는 녀석이 최상단 노드겠죠?)

*CONNECT BY PRIOR -> 자식과 부모를 명시하는 부분 N이 자식, P가 부모, 자식이 왼쪽 부모가 오른쪽

*LEVEL -> 그림1처럼 각 노드의 레벨을 보여준다

 

레벨의 최댓값과 최솟값을 구하면 루트 노드와 리프 노드를 구할 수 있고 나머지는 Inner로 처리하는 case 문을 사용하여 풀면 된다

 

. 

.

.

다 풀고 찾아보니 이런 계층형 쿼리 함수도 있었다..^^

<문제 풀이 2>

 

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

*CONNECT_BY_ROOT -> 최상위 노드 즉, 루트 노드를 반환하는 함수

*CONNCET_BY_ISLEAF -> 리프 노드를 알려주는 함수, 리프노드면 1 아니면 0을 반환