SQL - Binary Search Tree

Problem Statement

You are given a table, BST, containing two columns: N and P, where N represents the value of a node in BST, and P is the parent of N.

Write a query to find the node type of BST 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 Leaf

Explanation

The BST below illustrates the sample:

Query 

select  N,

case

  when P is null then 'Root'

  else

      decode((Select count(1)

              from BST

              Where N!=b.N

              connect by prior N=P

              start with N=b.N),0,'Leaf','Inner')

end "Leaf V"

from    BST b order by 1;

Your Output (stdout)

1 Leaf 
2 Inner 
3 Leaf 
4 Inner 
5 Leaf 
6 Inner 
7 Leaf 
8 Leaf 
9 Inner 
10 Leaf 
11 Inner 
12 Leaf 
13 Inner 
14 Leaf 
15 Root