Hackerrank - Calculating Leaf, Inner and Root Nodes in a Tree with SQL

Binary Trees make up a large part of computer science, but in this case, it is a simple SQL question asked by our friends at hackerrank.

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.

In the above example, 5 would be the root node, 1,3,6, and 9 are the leaf nodes and 2 and 8 are the inner nodes.

How do we calculate this with SQL?

Consider the following code:

WITH NODES AS (

SELECT *

FROM BST

)

,

ROOT_NODE AS (

SELECT N

FROM NODES

WHERE P IS NULL

)

,

LEAF_NODES AS (

SELECT N

FROM NODES

EXCEPT

SELECT P

FROM NODES

)

,

INNER_NODES AS (

SELECT N

FROM NODES

EXCEPT

(SELECT N

FROM LEAF_NODES UNION ALL

SELECT N

FROM ROOT_NODE)

)

SELECT N, type_of_node

from (

SELECT N, 'Leaf' as type_of_node

FROM LEAF_NODES UNION ALL

SELECT N, 'Root'

FROM ROOT_NODE UNION ALL

SELECT N, 'Inner'

FROM INNER_NODES) as x

order by n

The first CTE is just SELECTING the table allowing for multiple cases of recursion.

To get the leaf nodes it is a simple EXCEPT statement between the Parent and non-parent values.

The root node is calculated by selecting that node which does not have a parent value.

The inner nodes are simply those that aren't a parent or a leaf, another except was utilised in this case.

A series of unions with an order by just puts the records in the manner that the question asks for them.