Hacker Rank Challenge Binary Tree Nodes

Hi Everyone,

Today I will be going over how I solved the Hacker Rank Challenge, Binary Tree Nodes, using SQL.

The Objective is to 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

BST table contains two columns: N and P, where N represents the value of a node in Binary Tree, and P is the parent of N.

Table BST

Below is a sample of the binary tree sample:

I noticed when observing the tree and the table, the ‘root’ is a the top of the tree. It’s nothing above it, therefore it has no parent and represented as null in the table.

Everything that is considered ‘inner’ in the tree has a parent and children. If the node has a parent, but no children that is a ‘leaf’.

Once I understood the requirements, I began writing my query. I used a case statement that said if p is null then return root. When the node value equaled a distinct parent from the bst table it was an inner value. If it equaled a parent value that mean it had children. Lastly, everything else would be a leaf. As it would not equal a parent because it has no children.

After I completed my case statement then I just returned the node value and ordered by the node value and that solve the challenge! Woohoo!

The final query looks like this:

select n, 
 case when p is null then ‘Root’
 when n in (select distinct p from bst) then ‘Inner’ 
 else ‘Leaf’ end
from bst
order by n;

I hope this helps anyone that is trying to solve this challenge. Until next time!