Question 54162 in Javascript Question posted in
A very good W3school tutorial can be found here.

Count children of specific type cumulatively for each tree node – Javascript

I am fighting with this issue and not succeeding. I have the following tree:

enter image description here

It has two types of nodes, question and category. The categories are bolded and the questions have a circle next to them. The numbers in the category must show the subcategory coun for that node(easy), but the problem is the other number which must show the sum of the number of question type nodes in the levels below that node in the tree. And I am not able to do it.

My current version(after many):

if (treeNode.children && treeNode.children.length) {
            treeNode.questionCount = 0;
            treeNode.subcategoryCount = treeNode.children
                .filter((item) => item.type === NODE_TYPES.CATEGORY).length;
            for (let i = 0; i < treeNode.children.length; i++) {
                treeNode.questionCount += enrichWithNumberOfSubcategoriesAndQuestions(treeNode.children[i]);
            }

        }
        if (treeNode.type === NODE_TYPES.QUESTION) {
            return 1;
        } else if (treeNode.type === NODE_TYPES.CATEGORY) {
            return treeNode.children
                .filter((item) => item.type !== NODE_TYPES.CATEGORY).length;
        }
        return 0;
Tags:

2

Answers


  1. 0

    Here’s an approach. We are defining a recursive function which returns the number of questions inside the node.

    const updateNodeSubCategoryAndQuestionsCount = (treeNode) => {
    if (!treeNode.children?.length) return 0;

    const subCategories = [];
    const questions = [];

    treeNode.children.forEach((acc, curr) => {
        if (curr.type === NODE_TYPES.QUESTION) {
            questions.push(curr);
        } else if (curr.type === NODE_TYPES.CATEGORY) {
            subCategories.push(curr);
        }
    });

    treeNode.subcategoryCount = subCategories.length;
    treeNode.questionCount =
        questions.length +
        subCategories.reduce((acc, subCategory) => {
            return acc + updateNodeSubCategoryAndQuestionsCount(subCategory);
        }, 0);

    return treeNode.questionCount;
};
    Login or Signup to reply.
  2. 0

    The main idea is that you should first make the recursive calls so you are sure the child nodes have their count properties correctly set, and only then use that information to set the current node’s counter.

    Here is an implementation. I added class definitions, a print function, and an initialisation of a tree based on your example. That way you can run this code here and verify it does the job:

    function enrichWithNumberOfSubcategoriesAndQuestions(treeNode) {
    // Subcategory count: easy:
    treeNode.subcategoryCount = treeNode.children?.filter?.(item =>
        item.type === NODE_TYPES.CATEGORY
    )?.length ?? 0;
    // Question count: First solve the problem for the child nodes...
    treeNode.children?.forEach?.(enrichWithNumberOfSubcategoriesAndQuestions);
    // Then count the current node (yes/no)
    treeNode.questionCount = +(treeNode.type === NODE_TYPES.QUESTION);
    // And aggregate the child counters upwards:
    for (const child of treeNode.children ?? []) {
        treeNode.questionCount += child.questionCount;
    }
}

function printTree(treeNode, indent="") {
    console.log(`${indent}${treeNode.title} (${treeNode.subcategoryCount})(${treeNode.questionCount})`);
    for (const child of treeNode?.children ?? []) {
        printTree(child, indent + "   ");
    }
}

const NODE_TYPES = {
    CATEGORY: 1,
    QUESTION: 2,
}

class Question {
    constructor(title) {
        this.title = title;
        this.type = NODE_TYPES.QUESTION;
    }
}

class Category {
    constructor(title, ...children) {
        this.title = title;
        this.type = NODE_TYPES.CATEGORY;
        if (children.length) this.children = children;
    }
}

// Demo
const tree = new Category("Test",
    new Category("Test2",
        new Category("Beverages", 
            new Category("Internet-Usage",
                new Category("Cars",
                    new Question("question_1"),
                    new Question("question_2")
                ),
            ),
            new Category("Hobbies and Leisure"),
            new Category("Traveling")
        ),
        new Category("Education"),
        new Category("Electronics"),
        new Category("General Information"),
        new Category("Health"),
        new Category("HH Utilities & Responsibilities"),
    )
);

enrichWithNumberOfSubcategoriesAndQuestions(tree);
printTree(tree);
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search