Uber SQL interview questions – Leetcode 608 – Tree Node

Problem Description –

Given a table tree, id is identifier of the tree node and p_id is its parent node’s id.

Each node in the tree can be one of three types:

• Leaf: if the node is a leaf node.
• Root: if the node is the root of the tree.
• Inner: If the node is neither a leaf node nor a root node.

Write a query to print the node id and the type of the node. Sort your output by the node id. The result for the above sample is:

Explanation

• Node ‘1’ is root node, because its parent node is NULL and it has child node ‘2’ and ‘3’.
• Node ‘2’ is inner node, because it has parent node ‘1’ and child node ‘4’ and ‘5’.
• Node ‘3’, ‘4’ and ‘5’ is Leaf node, because they have parent node and they don’t have child node.

And here is the image of the sample tree as below:

Note

If there is only one node on the tree, you only need to output its root attributes.

Difficulty Level – Medium

Problem Link – https://leetcode.com/problems/tree-node/

Solution –

SELECT 
    id,
    CASE WHEN p_id IS NULL THEN 'Root'
         WHEN id IN (SELECT p_id FROM tree) THEN 'Inner'
         ELSE 'Leaf'
    END AS Type
FROM tree

The root node doesn’t have any parent node means root nodes value will be null in the p_id column. So, when sql evaluate the first case statement, for id 1, it will assign the value ‘Root’ as for this id, the value in the p_id column is null.

And we know that the Node 2 is a inner node because it has a parent node 1 and two child nodes 4 and 5. To cover this case, first we select all the ids from the p_id column which gives us –

select p_id FROM tree

So, the unique ids in this column are 1 and 2. So, when id will be among any one of these unique values, CASE statement will assign the value of ‘Inner’. Because as we know that CASE statement runs from top to bottom, so when we evaluate the first row for id 1, SQL will assign the value ‘Root’ instead of ‘inner’ as this case statement WHEN p_id IS NULL THEN 'Root' will be evaluated before the second one. But when the cursor will be on second row for id 2, the result will be ‘inner’ as id 2 is equal to one of the two unique p_id values.

And since ids 3, 4, 5 , none of them equals to two unique values in the p_id column the second case statement and neither for these id, the value in p_id column is null the first case statement, So sql will assign th evalue of ‘Leaf’ as described in the ELSE case.