Binary Search Tree - Hackerrank

Identifying Node Types in a Binary Search Tree Using SQL

In this blog post, we will explore how to identify the types of nodes in a Binary Search Tree (BST) using SQL. The table BST contains two columns: N and P, where N represents the value of a node in the Binary Tree, and P is the parent of N. We aim to find the node type of each node, ordered by the value of the node.

Problem Statement

You are given a table, BST, containing two columns:

• N: Represents the value of a node in the Binary Tree.

• P: Represents the parent of N.

You need to write a query to determine the node type of each node, ordered by the value of the node. The output should be one of the following for each node:

• Root: If the node is a root node.

• Leaf: If the node is a leaf node.

• Inner: If the node is neither a root nor a leaf node.

Sample Input

Sample Output

1 Leaf
2 Inner
3 Leaf
5 Root
6 Leaf
8 Inner
9 Leaf

Explanation

The Binary Tree below illustrates the sample:

SQL Query to Solve the Problem

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

Explanation of the SQL Query:
Root Nodes:
A node is identified as a root node if its parent (P) is NULL.
Leaf Nodes:
A node is identified as a leaf node if it does not appear as a parent (P) in the BST table. This is determined by checking if N is not in the list of distinct parent nodes.
Inner Nodes:
A node is identified as an inner node if it is neither a root nor a leaf node.
Query Breakdown:
SELECT N, selects the value of the node.
CASE statement is used to determine the NodeType:
WHEN P IS NULL THEN 'Root' checks if the node is a root node.
WHEN N NOT IN (SELECT DISTINCT P FROM BST) THEN 'Leaf' checks if the node is a leaf node.
ELSE 'Inner' categorizes the remaining nodes as inner nodes.
The ORDER BY N clause ensures that the output is ordered by the value of the node.

Conclusion
This SQL query effectively classifies each node in a Binary Search Tree as either a Root, Leaf, or Inner node based on their relationships. By leveraging SQL's powerful querying capabilities, we can efficiently determine the type of each node and output the results in a structured format.


**  Please do subscribe my blog for future updates and share with your friends, if you find this informative **