[HackerRank] Binary Tree Nodes

WITH RECURSIVE (CTE) 로 Level 구하기 !!! 매우 중요!

 

Question

 

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:

 

Point

 

• RECURSIVE 구문을 통해 Level을 입력한 후 마지막 node (leaf) 의 레벨이 적힌 열(MAX_LV)을 생성한다.
• 1레벨을 'Root', 마지막 레벨을 'Leaf'로 입력하고 나머진 Inner로 넣어준다.

 

Code

 

WITH RECURSIVE GENERATION AS(
    SELECT N, P, 1 AS LV
        FROM BST
        WHERE P IS NULL
    UNION ALL
    SELECT C.N, C.P, LV + 1
        FROM BST C
        JOIN GENERATION G
          ON C.P = G.N
),
GEN_WITH_MAX AS(
SELECT *, MAX(LV) OVER() AS MAX_LV
FROM GENERATION
)
SELECT N,
        CASE
            WHEN LV = 1 THEN 'Root'
            WHEN LV = MAX_LV THEN 'Leaf'
            ELSE 'Inner'
        END AS 'NODE'
FROM GEN_WITH_MAX
ORDER BY 1

 

now me

On my github