PROBLEM STATEMENT:
You are given a table, BTREE, containing two columns: Value and Parent, where ‘Value’ represents the value of a node in Binary Tree, and ‘Parent’ is the parent of ‘Value’ node. Below is the DDL of table.
CREATE TABLE BTREE
(
Value Integer,
Parent Integer
);
After creating table, insert below records into the table.
INSERT INTO BTREE(VALUE,PARENT) VALUES(1,2);
INSERT INTO BTREE(VALUE,PARENT) VALUES(3,2);
INSERT INTO BTREE(VALUE,PARENT) VALUES(6,8);
INSERT INTO BTREE(VALUE,PARENT) VALUES(9,8);
INSERT INTO BTREE(VALUE,PARENT) VALUES(2,5);
INSERT INTO BTREE(VALUE,PARENT) VALUES(8,5);
INSERT INTO BTREE(VALUE,PARENT) VALUES(5,NULL);
COMMIT;
So `SELECT * FROM BTREE` would look like:
| Value | Parent |
|---|---|
| 1 | 2 |
| 3 | 2 |
| 6 | 8 |
| 9 | 8 |
| 2 | 5 |
| 8 | 5 |
| 5 | NULL |
Below is the sample binary tree representation.
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.
Expected output:
| Value | Type |
|---|---|
| 1 | Leaf |
| 2 | Inner |
| 3 | Leaf |
| 5 | Root |
| 6 | Leaf |
| 8 | Inner |
| 9 | Leaf |
SOLUTION:
SELECT a.value,
CASE
WHEN a.parent IS NULL THEN ‘Root’
WHEN a.value IN (SELECT parent
FROM btree) THEN ‘Inner’
ELSE ‘Leaf’
END
FROM btree a
ORDER BY a.value
