[SQL] HackerRank Binary Tree Nodes

 

 

1. 최적화 전 코드 (서브쿼리 사용)

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

 

• WHERE P IS NOT NULL
  : 없을 경우 NOT IN 에 NULL이 포함되어 모든 결과가 FALSE/UNKNOWN으로 처리됨
  
  
• 서브쿼리와 DISTINCT 함수 존재
  : 엔진/옵티마이저에 따라 서브쿼리가 반복 시행될 수 있음
  : DISTINCT도 정렬/해시 연산으로 비용이 듬

 

2. 서브쿼리를 JOIN 으로 대체

SELECT DISTINCT A.N, CASE
            WHEN A.P IS NULL THEN 'Root'
            WHEN B.N IS NULL THEN 'Leaf'
            ELSE 'Inner'
          END AS VN
FROM BST A
LEFT JOIN BST B
ON A.N = B.P 
ORDER BY A.N

• 두 개의 BST 테이블을 JOIN하여 자식 노드가 null 이면 'Leaf' 로 판단하도록 쿼리 수정
  : 서브쿼리 반복 시행 문제를 해결