Hello coders, today we are going to solve Binary Tree Nodes HackerRank Solution in 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.
| Column | Type |
|---|---|
| N | Integer |
| P | Integer |
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
| N | P |
|---|---|
| 1 | 2 |
| 3 | 2 |
| 6 | 8 |
| 9 | 8 |
| 2 | 5 |
| 8 | 5 |
| 5 | null |
Sample Output
1 Leaf
2 Inner
3 Leaf
5 Root
6 Leaf
8 Inner
9 LeafSolution – Binary Tree Nodes in SQL
MySQL
SELECT N, IF(P IS NULL,"Root",IF((SELECT COUNT(*) FROM BST WHERE P=B.N)>0,"Inner","Leaf")) FROM BST AS B ORDER BY N;
Disclaimer: The above Problem (Binary Tree Nodes) is generated by Hacker Rank but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.
SELECT N, IF(P IS NULL,”Root”,IF((SELECT COUNT(*) FROM BST WHERE P=B.N)>0,”Inner”,”Leaf”)) FROM BST AS B ORDER BY N;
PLEASE explain P=B.N)>0, what is B here and What’s the meaning of B.N
SELECT N: This selects the “N” column from the “BST” table, which likely represents the value of each node in the binary search tree.
IF(P IS NULL, “Root”, …: This is a conditional statement that checks if the “P” column (representing the parent node) is NULL. If the parent node is NULL, it means the current node is the root of the tree. In that case, the value “Root” is returned for this node.
IF((SELECT COUNT(*) FROM BST WHERE P=B.N)>0, “Inner”, …: This is another conditional statement that checks if the current node has any child nodes. It does this by running a subquery (SELECT COUNT(*) FROM BST WHERE P=B.N) that counts the number of nodes in the “BST” table where the “P” column matches the “N” value of the current node. If this count is greater than 0, it means the node has child nodes and is therefore an inner node. In that case, the value “Inner” is returned for this node.
“Leaf”: If neither of the previous conditions is true, it means the node is neither a root nor an inner node, so it must be a leaf node. In that case, the value “Leaf” is returned for this node.
FROM BST AS B: This clause specifies that the query is performed on the “BST” table and gives it an alias “B” to refer to the table in the rest of the query.
ORDER BY N: This sorts the results based on the “N” column in ascending order, which would list the nodes in numerical order.
In summary, the query returns a list of nodes from the “BST” table along with their corresponding categories (“Root,” “Inner,” or “Leaf”) based on their parent-child relationships in the binary search tree. The result is ordered by the node values in ascending order.
SELECT N, CASE
WHEN P IS NULL THEN ‘Root’
WHEN N IN (SELECT DISTINCT P FROM BST WHERE P IS NOT NULL) THEN ‘Inner’
ELSE ‘Leaf’
END
FROM BST
ORDER BY N;