Frontend School

Retrieve All Descendant Categories

DSA
easy

Retrieve All Descendant Categories

Easy
Recursion
Tree
Depth-First Search

Overview

Blinkit's product catalog is extensive and organized into a hierarchical structure of categories. For example, "Beverages" might have "Juices" and "Soft Drinks" as subcategories, and "Juices" might further have "Fresh Juices" and "Packaged Juices". Maintaining and navigating this structure efficiently is crucial for inventory management, personalized recommendations, and user experience.

What you need to do / Task

Your task is to implement a function that, given a starting category ID and a flat list of all categories, returns a list of all descendant category IDs. This includes direct subcategories, their subcategories, and so on, down to the deepest level.

Input & output

Function Signature:

function getAllDescendantCategoryIds(categoryId: number, categories: Category[]): number[]

Input:

  • categoryId: A number representing the ID of the parent category for which we need to find all descendants.
  • categories: An array of Category objects. Each Category object has the following structure:
    interface Category {
        id: number;
        name: string; // A descriptive name, not used for logic
        parentId: number | null; // The ID of the parent category, or null if it's a top-level category
    }
    

Output:

  • A number[] representing a list of unique IDs of all categories that are descendants (direct or indirect) of the given categoryId. The order of IDs in the output array does not matter.

Clarifications

  • The categories array can contain categories that are not descendants of the categoryId, or even categories that are ancestors. You should only return descendants.
  • The input categoryId itself should NOT be included in the output list.
  • If a categoryId does not exist or has no descendants, an empty array should be returned.
  • All category IDs are positive integers. parentId can be null for root categories.

Examples

1

Example 1

Input:

categoryId = 1, categories = [{"id":1,"name":"Electronics","parentId":null},{"id":2,"name":"Mobiles","parentId":1},{"id":3,"name":"Smartphones","parentId":2},{"id":4,"name":"Laptops","parentId":1}]

Output:

[2,3,4]

Note:

Category 1 (Electronics) has direct children 2 (Mobiles) and 4 (Laptops). Category 2 (Mobiles) has direct child 3 (Smartphones). All are descendants of 1.

2

Example 2

Input:

categoryId = 3, categories = [{"id":1,"name":"Electronics","parentId":null},{"id":2,"name":"Mobiles","parentId":1},{"id":3,"name":"Smartphones","parentId":2},{"id":4,"name":"Laptops","parentId":1}]

Output:

[]

Note:

Category 3 (Smartphones) has no subcategories, so an empty array is returned.

3

Example 3

Input:

categoryId = 1, categories = [{"id":1,"name":"Groceries","parentId":null},{"id":2,"name":"Fruits","parentId":1},{"id":3,"name":"Apples","parentId":2},{"id":4,"name":"Vegetables","parentId":1},{"id":5,"name":"Dairy","parentId":null},{"id":6,"name":"Milk","parentId":5}]

Output:

[2,3,4]

Note:

Categories 5 (Dairy) and 6 (Milk) are not descendants of category 1 (Groceries) and are correctly excluded from the result.

Constraints

Constraints & assumptions

  • The total number of categories (N) in the categories array will be between 0 and 100.
  • Category IDs will be unique within the categories array.
  • categoryId will be a positive integer.
  • The category hierarchy will not contain cycles (i.e., it forms a directed acyclic graph, specifically a forest).

What interviewers evaluate

  • Correctness: Does the solution correctly identify all descendant categories?
  • Recursive Logic: Is recursion used effectively to traverse the category hierarchy?
  • Clarity & Readability: Is the code well-structured, easy to understand, and appropriately commented?
  • Edge Cases: Does the solution handle cases like a category having no children, or the input categoryId not existing?

Loading editor...