Find all the leaf nodes below a subtree in a Tree structure in sql server

Question

I've a tree structure, and its subsequent assignment table for customer categories in an sql server database.

CustomerCategory (CategoryID, ParentId)
CustomerInCategory(CustomerID, CategoryID)

If a CustomerCategory has any customer assigned to it, we can't add another subcategory to it. So, Customer can only be added to the lowest level in every sub tree. In other sense, the result of this query

SELECT * FROM `CustomerCategory` WHERE `CategoryId` NOT IN 
(SELECT DISTINCT `parentid` FROM `CustomerCategory` WHERE `parentid` IS NOT NULL)

would yield leaf nodes. The Other thing is that, this tree might have subtrees of different levels, and we also, don't want to bound the number of levels in anyway, however, our users won't need more than 10 levels. Consider this as an illustration

CategoryID------ParentID---------------Name
1               NULL                   All Customers
2               1                      Domestic
3               1                      International
4               2                      Independent Retailers
5               2                      Chain Retailers
6               2                      Whole Sellers
7               5                      A-Mart
8               5                      B-Mart
9               4                      Grocery Stores
10              4                      Restaurants
11              4                      Cafes

CustomerID---------CustomerName----------Category
1                  Int.Customer#1               3
2                  Int.Customer#2               3
3                  A-Mart.Branch#1              7
4                  A-Mart.Branch#2              7
5                  B-Mart.Branch#1              8
6                  B-Mart.Branch#2              8
7                  Grocery#1                    9
8                  Grocery#2                    9
9                  Grocery#3                    9
10                 Restaurant#1                 10
11                 Restaurant#2                 10
12                 Cafe#1                       11
13                 Wholeseller#1                6
14                 Wholeseller#2                6

My requirement is something like this, "Given a node in Categories, Return All the Customers attached to any node below it".

How can I do it with sql?

Obviously this can be done with a recursive call in the code, but how can we do it in t-sql (without calling a stored procedure several times or using text-based search)?

Can any body, Use a CTE to solve this problem?

I have a result set of something like this in mind

CustomerID--------Customer Name----------------CategoryId----------CAtegoryName

12                Cafe#1                       11                  Cafes
12                Cafe#1                       4                   IndependentRetailers
12                Cafe#1                       2                   Demoestic
12                Cafe#1                       1                   AllCustomers
.
.
.
4                 A-Mart.Branch#2              7                  A-Mart
4                 A-Mart.Branch#2              5                  Chain Retailers
4                 A-Mart.Branch#2              2                  Domestic
4                 A-Mart.Branch#2              1                  All Customers
.
.
.
14                 Wholeseller#2               6                  WholeSellers
14                 Wholeseller#2               2                  Domestic
14                 Wholeseller#2               1                  All Customers

This is not necessarily a good Idea to layout a result like this, This would consume too much space, something that might not be required, yet, a search in such result set would be very fast. If I want to find all the customers below say categoryId = 2 , I would simply query

SELECT * FROM resultset where category ID = 2

Any suggestions to improve the data model is super welcomed! If It helps solving this problem.

Once again, I'm not fixated on this result set. Any other Suggestion that solves the problem, "Given a node in Categories, Return All the Customers attached to any node below it", is well accepted.

Answer 1

You can use a CTE to recursively build a table containing all the parent-child relationships and use the where clause to get only the subtree you need (in my example, everyting under CategoryId 5) :

WITH CategorySubTree AS (
    SELECT cc.CategoryId as SubTreeRoot,
            cc.CategoryId 
            FROM CustomerCategory cc
UNION ALL
    SELECT cst.SubTreeRoot, cc.CategoryId
        FROM CustomerCategory cc
        INNER JOIN CategorySubTree cst ON cst.CategoryId = cc.parentId
)
SELECT cst.CategoryId
FROM CategorySubTree cst
WHERE cst.SubTreeRoot = 5

You can modify this query to add whatever you need, for example, to get customers linked to the category nodes in the subtree :

WITH CategorySubTree AS (
    SELECT cc.CategoryId as SubTreeRoot,
            cc.CategoryId 
            FROM CustomerCategory cc
UNION ALL
    SELECT cst.SubTreeRoot, cc.CategoryId
        FROM CustomerCategory cc
        INNER JOIN CategorySubTree cst ON cst.CategoryId = cc.parentId
)
SELECT cst.CategoryId,cic.CustomerId
FROM CategorySubTree cst
        INNER JOIN CustomerInCategory cic ON cic.CategoryId = cst.CategoryId
WHERE cst.SubTreeRoot = 5

And of course you can join further tables to get labels and other needed information.