Binary Tree Node Type Query on HackerRank SQL
Problem
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
Solution:
SELECT N,
CASE
WHEN P IS NULL THEN 'Root'
WHEN N IN (SELECT P FROM BST) THEN 'Inner'
ELSE 'Leaf'
END
FROM BST
ORDER by N;
Explanation:
- SELECT N, ... FROM BST: This part of the query selects the column N from the table BST. N represents a node in the BST.
- CASE statement is used to categorize each node.
- WHEN P IS NULL THEN 'Root': If the parent P of node N is NULL, it means N is the root node because the root node has no parent.
- WHEN N IN (SELECT P FROM BST) THEN 'Inner': If N appears as a parent in the table BST, it means N is an inner node because it has at least one child.
- ELSE 'Leaf': If N is neither a root nor an inner node, it is categorized as a leaf node, meaning it has no children.
- (SELECT P FROM BST): This subquery selects all parent nodes P from the table BST. This is used to check if a node N is an inner node
- ORDER BY N: The results are ordered by node N in ascending order.
