CODEWITHSUNDEEP
sqlmysqlbinary-tree
prasanna kumar
prasanna kumar

Reputation: 293

Classifying binary tree nodes using SQL

I am trying to solve the problem mentioned at the below link:

https://www.hackerrank.com/challenges/binary-search-tree-1/problem

I have written the following code. Please help me where i am going wrong

Select q.Node,case
              WHEN q.Node NOT IN q.Parent THEN 'Leaf' 
              WHEN q.Node IN q.Parent AND q.Node NOT IN q.Higher_Parent THEN 'Inner'
              WHEN q.Node IN q.Parent AND q.Node IN q.Higher_Parent THEN 'Root'
              END as NodeType
from (
SELECT B1.N as Node,B1.P as Parent,B2.P as Higher_Parent FROM 
BST B1 INNER JOIN BST B2 
ON B1.P = B2.N
ORDER BY Node ASC
) q

N P HP
1 2 5
2 5 NULL
3 2 5
6 8 5
8 5 NULL
9 8 5

Where should I modify the above code to work. Sure there are other concise codes for the same problem but please help me with this code for learning purpose.

Upvotes: 0

Views: 11599

Answers (7)

Penny Liu
Penny Liu

Reputation: 17468

Here’s a explanation of the query:

SELECT N,
(CASE
   WHEN P IS NULL THEN 'Root'
   WHEN N IN (SELECT DISTINCT P FROM BST) THEN 'Inner'
   ELSE 'Leaf'
END) AS Output
FROM BST
ORDER BY N;

CASE Statement:

  • If P IS NULL: Classify the node as 'Root' (it has no parent).
  • If N IN (SELECT DISTINCT P FROM BST): Classify the node as 'Inner' (it is a parent to at least one other node).
  • Otherwise: Classify the node as 'Leaf' (it is neither a root nor a parent).

Final Output

Binary Tree Nodes

Upvotes: 0

Sarath Puppala
Sarath Puppala

Reputation: 11

-- SQL SERVER working Solution

select N,
case 
when p is null then "Root"
when N in (select P from BST) THEN "Inner"
Else "Leaf" end as "P"
from BST
ORDER BY N;

Upvotes: 1

Ankit
Ankit

Reputation: 11

See the below code. It might be easy to comprehend.

select n, 'Leaf' as nodename from bst
where n not in (select distinct p from bst where p is not null)
union
select n, 'Root' as nodename from bst
where p is null
union
select n, 'Inner' as nodename from bst
where n in (select distinct p from bst)
and p is not null
order by n asc;

Upvotes: 0

Bijay Shakya
Bijay Shakya

Reputation: 61

You can use CASE statement as follows:

SELECT N, CASE WHEN P IS NULL THEN 'Root' 
WHEN(SELECT COUNT(*) FROM BST WHERE P = T.N) > 0 THEN 'Inner'
ELSE 'Leaf'
END
FROM BST T
ORDER BY N;

Upvotes: 2

Kumar Attangudi Perichiappan
Kumar Attangudi Perichiappan

Reputation: 26

You can use if else to solve it as well:

SELECT B.N, IF(B.P IS NULL, 'Root', IF((SELECT COUNT(*) FROM BST AS A WHERE A.P=B.N)>0,'Inner','Leaf')) 
FROM BST AS B 
ORDER BY B.N;

Upvotes: 0

Ajay Gupta
Ajay Gupta

Reputation: 1855

You need to find the child instead of the higher parent.

Select distinct c.n, 
        case when c.P is null then 'Root' 
             when b1.N is null then 'Leaf'
             else 'Inner' end
from BST c
left join BST b1
on c.N = b1.P
order by c.n

Upvotes: 0

Paul Spiegel
Paul Spiegel

Reputation: 31812

select n.n,
  case 
    when max(p.n) is null then 'root'
    when max(c.n) is null then 'leaf'
    else 'inner'
  end as type
from bst n
left join bst p on p.n = n.p
left join bst c on c.p = n.n
group by n.n

Result:

| n |  type |
|---|-------|
| 1 |  leaf |
| 2 | inner |
| 3 |  leaf |
| 5 |  root |
| 6 |  leaf |
| 8 | inner |
| 9 |  leaf |

Demo: http://sqlfiddle.com/#!9/ba3c76/1

Upvotes: 0

Related Questions