BINARY TREE NODES QUESTION AND SOLUTION WITH QUERY

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:

ValueParent
12
32
68
98
25
85
5NULL

Below is the sample binary tree representation.

btree-sample

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:

ValueType
1Leaf
2Inner
3Leaf
5Root
6Leaf
8Inner
9Leaf

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

Comments

comments

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: