[SQL] Binary Tree Nodes

μˆœλ™Β·2022λ…„ 5μ›” 16일
0

βœ… 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


πŸ’» 풀이

SELECT
    B1.N,
    (CASE
        WHEN B1.P IS NULL THEN "Root"
        WHEN B3.P IS NOT NULL THEN "Leaf"
        ELSE "Inner"
    END) AS result
FROM BST AS B1 LEFT OUTER JOIN BST AS B2 ON B1.P = B2.N
    LEFT OUTER JOIN BST AS B3 ON B2.P = B3.N
ORDER BY B1.N ASC;

πŸ’‘ Idea

SELF JOIN 방법을 μ΄μš©ν–ˆλ‹€. ν•˜μ§€λ§Œ MySQLμ—μ„œλŠ” ν•΄λ‹Ή ν•¨μˆ˜λ₯Ό μ§€μ›ν•˜μ§€ μ•ŠμœΌλ―€λ‘œ LEFT OUTER JOIN ν•¨μˆ˜λ₯Ό μ€‘μ²©ν•˜μ—¬ ν’€μ—ˆλ‹€.

μ˜ˆμ‹œλ₯Ό λ“€μžλ©΄ λΆ€ν•˜ 직원듀을 λ‹΄λ‹Ήν•˜λŠ” 상사가 μžˆλ‹€κ³  μƒκ°ν•˜λ©΄ λœλ‹€.

λΆ€ν•˜μƒμ‚¬λΆ€ν•˜μƒμ‚¬
1224

λΆ€ν•˜ 1의 μƒμ‚¬λŠ” 2이고, 2의 μƒμ‚¬λŠ” 4이닀.
λ§Œμ•½ 4κ°€ 직μž₯ λ‚΄μ˜ 제일 높은 μ§μœ„λ₯Ό κ°€μ‘Œλ‹€κ³  κ°€μ •ν•˜λ©΄, 4의 μƒμ‚¬λŠ” μ‘΄μž¬ν•˜μ§€ μ•ŠκΈ° λ•Œλ¬Έμ— NULL이 μž…λ ₯λœλ‹€.

λ”°λΌμ„œ μœ„μ˜ 원리λ₯Ό μ΄μš©ν•˜μ—¬ ν’€μ—ˆλ‹€.


0개의 λŒ“κΈ€