Search⌘ K
AI Features
Home
Courses
Grokking the SQL Interview Patterns

Recursive Tree

Explore how to write recursive SQL queries using common table expressions to traverse hierarchical data structures such as customer referral networks. Understand the recursive tree pattern to retrieve multilevel parent-child relationships, write scalable queries, and solve complex hierarchical data problems.

We'll cover the following...

Every modern business has to deal with hierarchical data.

Think about an organization chart, product categories with subcategories, or a customer referral network. Imagine we want to find all the people referred directly or indirectly by a particular customer. This kind of recursive relationship is not something we can easily handle with a standard join or filter.

That is where the recursive tree pattern comes in.

In this lesson, we’ll learn how to query hierarchical data using CTE SQL (recursive common table expressions). We’ll break down the structure of recursive queries, learn how to think in terms of tree traversal, and write SQL that can drill through multiple levels of a relationship.

By the end, we’ll be able to answer complex questions about parent-child chains and multilevel hierarchies in a clean and scalable way.

In this lesson, we will:

  • Understand when and why to use recursive queries in SQL.

  • Learn the structure of a recursive CTE and how it works step-by-step.

  • Use recursive queries to explore hierarchical relationships, such as customer referral chains.

  • Write, read, and debug recursive SQL queries confidently.

Pattern overview

Category:

  • Sequencing & Hierarchical Patterns

Intent:

To retrieve hierarchical, parent-child, or tree-structured data using recursive queries.

Motivation:

Hierarchical relationships are everywhere in databases: employee-manager structures, referral systems, category-subcategory setups, and more. These relationships can't be fully explored with a simple join, especially when they go multiple levels deep. We need a pattern that can expand a tree-like structure as far as it goes. Using a CTE SQL pattern helps us follow these chains cleanly and efficiently.

Also known as:

  • Hierarchical queries

  • Tree traversal

  • Parent-child expansion

  • Recursive CTEs

Structure

WITH RECURSIVE TreeCTE (id, parent_id, level) AS (
    -- Anchor member: starting point
    SELECT id, parent_id, 1 AS level
    FROM   SomeTable
    WHERE  parent_id IS NULL  -- or other base condition
    UNION ALL
    -- Recursive member: self-join on CTE
    SELECT     child.id, child.parent_id, level + 1
    FROM       SomeTable AS child
    INNER JOIN TreeCTE AS parent ON child.parent_id = parent.id
)
SELECT * FROM TreeCTE;
Syntax for Recursive tree pattern

Keywords

WITH RECURSIVE, UNION ALL, anchor query, recursive query, hierarchy, parent-child, tree traversal

Problem structure

We use the Recursive Tree pattern when:

  • We need to traverse hierarchical or tree-structured data (e.g., categories, org charts, comment threads).

  • We start with a base case (anchor query) that selects the top-level or root nodes.

  • We use a recursive query that repeatedly joins the base result with itself to move through levels of the hierarchy.

  • The recursion continues until no more child records are found.

  • Look for keywords like: “hierarchy,” “levels,” “parent-child,” “nested structure,” or “walk the tree” to identify when this pattern applies.

Example use case: Customer referral network

Given the following structure of the Customers table:

Field

Type

CustomerID

int

CustomerName

varchar(50)

Email

varchar(50)

Phone

varchar(15)

Address

varchar(100)

LastLogin

date

CreatedAt

timestamp

CustomerTier

enum('New','Regular','VIP')

ReferralID

int

LoyaltyPoints

int

LastPurchaseDate

date

IsChurnRisk

tinyint(1)

Where CustomerID is the primary key and ReferralID is self-referencing to CustomerID.

The table contains information about customers. Let’s say we want to find all customers who were referred directly or indirectly by a specific customer (e.g., a customer with CustomerID = 1). We’ll use the Customers table, where the ReferralID column tracks who referred whom. Here's how we can explore this hierarchy:

Write a recursive CTE SQL query to generate a referral tree starting from CustomerID = 1.

For each customer in the tree, return:

  • CustomerID

  • CustomerName

  • ReferralID

  • Level (0 for the root customer, 1 for those they referred, 2 for referrals of referrals, etc.)

MySQL
WITH RECURSIVE ReferralTree AS (
    -- Anchor: Start from customer ID 1
    SELECT CustomerID,
           CustomerName,
           ReferralID,
           0 AS Level
    FROM   Customers
    WHERE  CustomerID = 1
    UNION ALL
    -- Recursive: Find customers referred by previous level
    SELECT     c.CustomerID,
               c.CustomerName,
               c.ReferralID,
               rt.Level + 1
    FROM       Customers c
    INNER JOIN ReferralTree rt ON c.ReferralID = rt.CustomerID
)
SELECT * FROM ReferralTree;

Related patterns

  • Join variants: Recursive queries often involve self-joins.

  • Set compare: Useful when comparing entire branches.

  • Deduplication: Helpful if cycles are present (recursive queries can loop infinitely without guardrails).

Exercises

Easy

1. Get all customers referred directly by CustomerID = 2

Given the following structure of the Customers table:

Field

Type

CustomerID

int

CustomerName

varchar(50)

Email

varchar(50)

Phone

varchar(15)

Address

varchar(100)

LastLogin

date

CreatedAt

timestamp

CustomerTier

enum('New','Regular','VIP')

ReferralID

int

LoyaltyPoints

int

LastPurchaseDate

date

IsChurnRisk

tinyint(1)

Where CustomerID is the primary key and ReferralID is self-referencing to CustomerID. The table contains information about customers. Write an SQL query to find all customers who were referred by Customer ID 2. Return all columns for these customers.

Sample output:

CustomerID CustomerName Email
4 Bob Brown bobbrown@example.com
7 Emily Davis emilyd@example.com
MySQL
-- Write your query here

If you’re stuck, click the “Show Solution” button.

2. List CustomerID and ReferralID for all customers.

Given the following structure of the Customers table:

Field

Type

CustomerID

int

CustomerName

varchar(50)

Email

varchar(50)

Phone

varchar(15)

Address

varchar(100)

LastLogin

date

CreatedAt

timestamp

CustomerTier

enum('New','Regular','VIP')

ReferralID

int

LoyaltyPoints

int

LastPurchaseDate

date

IsChurnRisk

tinyint(1)

Where CustomerID is the primary key and ReferralID is self-referencing to CustomerID. The table contains information about customers. Write an SQL query to return a list of all customers along with the ID of the customer who referred them (if any).

Sample output:

CustomerID ReferralID
1 NULL
2 NULL
MySQL
-- Write your query here

If you’re stuck, click the “Show Solution” button.

3. Show all customers without a referrer (roots of the tree).

Given the following structure of the Customers table:

Field

Type

CustomerID

int

CustomerName

varchar(50)

Email

varchar(50)

Phone

varchar(15)

Address

varchar(100)

LastLogin

date

CreatedAt

timestamp

CustomerTier

enum('New','Regular','VIP')

ReferralID

int

LoyaltyPoints

int

LastPurchaseDate

date

IsChurnRisk

tinyint(1)

Where CustomerID is the primary key and ReferralID is self-referencing to CustomerID. The table contains information about customers. Write an SQL query to find all customers who were not referred by anyone (i.e., their ReferralID is NULL). Return the CustomerID and CustomerName.

Sample output:

CustomerID CustomerName
1 John Doe
2 Jane Smith
MySQL
-- Write your query here

If you’re stuck, click the “Show Solution” button.

4. How many customers did customer 1 refer directly?

Given the following structure of the Customers table:

Field

Type

CustomerID

int

CustomerName

varchar(50)

Email

varchar(50)

Phone

varchar(15)

Address

varchar(100)

LastLogin

date

CreatedAt

timestamp

CustomerTier

enum('New','Regular','VIP')

ReferralID

int

LoyaltyPoints

int

LastPurchaseDate

date

IsChurnRisk

tinyint(1)

Where CustomerID is the primary key and ReferralID is self-referencing to CustomerID. The table contains information about customers. Write an SQL query to count how many customers were referred by customer with ID = 1.

Sample output:

COUNT(*)
5
MySQL
-- Write your query here

If you’re stuck, click the “Show Solution” button.

5. List customers who were referred by someone who was referred by customer 1.

Given the following structure of the Customers table:

Field

Type

CustomerID

int

CustomerName

varchar(50)

Email

varchar(50)

Phone

varchar(15)

Address

varchar(100)

LastLogin

date

CreatedAt

timestamp

CustomerTier

enum('New','Regular','VIP')

ReferralID

int

LoyaltyPoints

int

LastPurchaseDate

date

IsChurnRisk

tinyint(1)

Where CustomerID is the primary key and ReferralID is self-referencing to CustomerID. The table contains information about customers. Write an SQL query to find the IDs, names, and emails of all customers who were referred by someone who was referred by Customer 1 (i.e., second-level referrals).

Sample output:

CustomerID CustomerName Email
11 Ivy King ivyking@example.com
25 Wendy Young wendyy@example.com
MySQL
-- Write your query here

If you’re stuck, click the “Show Solution” button.

Medium

1. Build a recursive tree starting from customer 2.

Given the following structure of the Customers table:

Field

Type

CustomerID

int

CustomerName

varchar(50)

Email

varchar(50)

Phone

varchar(15)

Address

varchar(100)

LastLogin

date

CreatedAt

timestamp

CustomerTier

enum('New','Regular','VIP')

ReferralID

int

LoyaltyPoints

int

LastPurchaseDate

date

IsChurnRisk

tinyint(1)

Where CustomerID is the primary key and ReferralID is self-referencing to CustomerID.

The table contains information about customers. Write a recursive SQL query to find the full referral tree starting from Customer ID = 2. Return the CustomerID, CustomerName, ReferralID, and their Level in the referral hierarchy (0 = root).

Sample output:

CustomerID CustomerName ReferralID Level
2 Jane Smith NULL 0
4 Bob Brown 2 1
MySQL
-- Write your query here

If you’re stuck, click the “Show Solution” button.

2. Add depth level and sort by referral chain.

Given the following structure of the Customers table:

Field

Type

CustomerID

int

CustomerName

varchar(50)

Email

varchar(50)

Phone

varchar(15)

Address

varchar(100)

LastLogin

date

CreatedAt

timestamp

CustomerTier

enum('New','Regular','VIP')

ReferralID

int

LoyaltyPoints

int

LastPurchaseDate

date

IsChurnRisk

tinyint(1)

Where CustomerID is the primary key and ReferralID is self-referencing to CustomerID. The table contains information about customers. Write a recursive SQL query to return the referral chain starting from CustomerID = 1. For each customer, return:

  • Their CustomerID, CustomerName, and ReferralID

  • Their depth in the referral hierarchy (0 for the original customer)

Sort the output by Depth.

Sample output:

CustomerID CustomerName ReferralID Depth
1 John Doe NULL 0
3 Alice Johnson 1 1
MySQL
-- Write your query here

If you’re stuck, click the “Show Solution” button.

3. Find the total number of people referred by customer 1 (any level).

Given the following structure of the Customers table:

Field

Type

CustomerID

int

CustomerName

varchar(50)

Email

varchar(50)

Phone

varchar(15)

Address

varchar(100)

LastLogin

date

CreatedAt

timestamp

CustomerTier

enum('New','Regular','VIP')

ReferralID

int

LoyaltyPoints

int

LastPurchaseDate

date

IsChurnRisk

tinyint(1)

Where CustomerID is the primary key and ReferralID is self-referencing to CustomerID. The table contains information about customers. Write a recursive SQL query to count the total number of customers that were directly or indirectly referred by CustomerID = 1.

Exclude CustomerID = 1 from the final count.

Sample output:

COUNT(*) - 1
8
MySQL
-- Write your query here

If you’re stuck, click the “Show Solution” button.

4. Limit referral depth to 2 levels.

Given the following structure of the Customers table:

Field

Type

CustomerID

int

CustomerName

varchar(50)

Email

varchar(50)

Phone

varchar(15)

Address

varchar(100)

LastLogin

date

CreatedAt

timestamp

CustomerTier

enum('New','Regular','VIP')

ReferralID

int

LoyaltyPoints

int

LastPurchaseDate

date

IsChurnRisk

tinyint(1)

Where CustomerID is the primary key and ReferralID is self-referencing to CustomerID.

The table contains information about customers. Write a recursive SQL query to retrieve all customers referred (directly or indirectly) by CustomerID = 1, up to 2 levels deep. Return their CustomerID, CustomerName, ReferralID, and Depth level (0 for root, 1 for direct referral, 2 for referral of referral).

Sample output:

CustomerID CustomerName ReferralID Depth
1 John Doe NULL 0
3 Alice Johnson 1 1
MySQL
-- Write your query here

If you’re stuck, click the “Show Solution” button.

5. Track the full referral path (ID chain).

Given the following structure of the Customers table:

Field

Type

CustomerID

int

CustomerName

varchar(50)

Email

varchar(50)

Phone

varchar(15)

Address

varchar(100)

LastLogin

date

CreatedAt

timestamp

CustomerTier

enum('New','Regular','VIP')

ReferralID

int

LoyaltyPoints

int

LastPurchaseDate

date

IsChurnRisk

tinyint(1)

Where CustomerID is the primary key and ReferralID is self-referencing to CustomerID. The table contains information about customers. Write a recursive SQL query to trace the full referral path starting from CustomerID = 1. For each customer in the referral chain, return:

  • CustomerID

  • ReferralID

  • Path→a breadcrumb-like string of CustomerIDs in order of referral (e.g., 1 -> 3 -> 12)

Sample output:

CustomerID ReferralID Path
1 NULL 1
3 1 1 -> 3
MySQL
-- Write your query here

If you’re stuck, click the “Show Solution” button.

Hard

1. Detect circular referrals (shouldn’t exist).

Given the following structure of the Customers table:

Field

Type

CustomerID

int

CustomerName

varchar(50)

Email

varchar(50)

Phone

varchar(15)

Address

varchar(100)

LastLogin

date

CreatedAt

timestamp

CustomerTier

enum('New','Regular','VIP')

ReferralID

int

LoyaltyPoints

int

LastPurchaseDate

date

IsChurnRisk

tinyint(1)

Where CustomerID is the primary key and ReferralID is self-referencing to CustomerID. The table contains information about customers. Write a recursive SQL query to traverse all referral chains in the Customers table and prevent infinite recursion due to cyclic referrals. Track the full chain of referrals using a Path column and ensure no CustomerID appears more than once in a single chain.

Sample output:

CustomerID ReferralID Path
1 NULL 1
2 NULL 2
MySQL
-- Write your query here

If you’re stuck, click the “Show Solution” button.

2. List all customers who are part of any referral chain that begins with customer 2.

Given the following structure of the Customers table:

Field

Type

CustomerID

int

CustomerName

varchar(50)

Email

varchar(50)

Phone

varchar(15)

Address

varchar(100)

LastLogin

date

CreatedAt

timestamp

CustomerTier

enum('New','Regular','VIP')

ReferralID

int

LoyaltyPoints

int

LastPurchaseDate

date

IsChurnRisk

tinyint(1)

Where CustomerID is the primary key and ReferralID is self-referencing to CustomerID. The table contains information about customers. Write a recursive SQL query to find all customers referred (directly or indirectly) by CustomerID = 2. Return their IDs, names, and emails from the Customers table.

Sample output:

CustomerID CustomerName Email
2 Jane Smith janesmith@example.com
4 Bob Brown bobbrown@example.com
MySQL
-- Write your query here

If you’re stuck, click the “Show Solution” button.

3. Count how many customers have at least one indirect referral.

Given the following structure of the Customers table:

Field

Type

CustomerID

int

CustomerName

varchar(50)

Email

varchar(50)

Phone

varchar(15)

Address

varchar(100)

LastLogin

date

CreatedAt

timestamp

CustomerTier

enum('New','Regular','VIP')

ReferralID

int

LoyaltyPoints

int

LastPurchaseDate

date

IsChurnRisk

tinyint(1)

Where CustomerID is the primary key and ReferralID is self-referencing to CustomerID. The table contains information about customers. Write a recursive SQL query to compute how many customers were referred (directly or indirectly) by each top-level referrer (someone whose ReferralID IS NULL).

Return the RootID and the count of indirect referrals (TotalIndirects) Exclude root customers with no referrals.

Sample output:

RootID TotalIndirects
3 4
4 2
MySQL
-- Write your query here

If you’re stuck, click the “Show Solution” button.

4. Find the max referral depth starting from customer 1.

Given the following structure of the Customers table:

Field

Type

CustomerID

int

CustomerName

varchar(50)

Email

varchar(50)

Phone

varchar(15)

Address

varchar(100)

LastLogin

date

CreatedAt

timestamp

CustomerTier

enum('New','Regular','VIP')

ReferralID

int

LoyaltyPoints

int

LastPurchaseDate

date

IsChurnRisk

tinyint(1)

Where CustomerID is the primary key and ReferralID is self-referencing to CustomerID. The table contains information about customers. Write an SQL query to find the maximum depth of the referral chain starting from a specific customer (e.g., CustomerID = 1).

The initial customer is considered to be at Depth = 0.

Sample output:

MaxReferralDepth
3
MySQL
-- Write your query here

If you’re stuck, click the “Show Solution” button.

5. Show all referral chains of customer 1 with customer names instead of IDs.

Given the following structure of the Customers table:

Field

Type

CustomerID

int

CustomerName

varchar(50)

Email

varchar(50)

Phone

varchar(15)

Address

varchar(100)

LastLogin

date

CreatedAt

timestamp

CustomerTier

enum('New','Regular','VIP')

ReferralID

int

LoyaltyPoints

int

LastPurchaseDate

date

IsChurnRisk

tinyint(1)

Where CustomerID is the primary key and ReferralID is self-referencing to CustomerID. The table contains information about customers. Write a recursive SQL query to find the full referral paths by name starting from CustomerID = 1.
Each row should include the customer’s:

  • CustomerID

  • ReferralID

  • CustomerName

  • Path: a string showing the full referral chain

Sample output:

CustomerID ReferralID CustomerName Path
1 NULL John Doe John Doe
3 1 Alice Johnson John Doe -> Alice Johnson
MySQL
-- Write your query here

If you’re stuck, click the “Show Solution” button.

Recursive queries give us the ability to handle hierarchical structures in ways that would otherwise be extremely difficult with traditional SQL.

In this lesson, we learned how to work with recursive CTEs, starting from a base case and expanding down the chain of relationships step by step. We applied this to our referral network to trace how customers are connected, and even went further to limit depth, find paths, and detect cycles.

This pattern might feel abstract at first, but once we get comfortable with the structure, it opens up a new world of problem-solving in SQL. Recursive logic is powerful and elegant, and now it is in our toolkit. Keep going!