Finding all children of a node in a tree

In an E-commerce project, I had to address the problem of creating a coupon assigned for a specific category of products. If a type of category is chosen for a coupon then all the sub-categories of that will also be applied. My task was to create a logic to find all these sub-categories. To illustrate the logic behind this, we can consider the case with a tree.

The above tree can be represented as an array of objects. Where each object represents a node, each object is having an id and parent_node as fields.



let tree = [
    // root node
    {
        id: "A",
        parent_node: "",

    },
    {
        id: "B",
        parent_node: "A",

    },
    {
        id: "C",
        parent_node: "A",

    },
    {
        id: "D",
        parent_node: "B",

    },
    {
        id: "E",
        parent_node: "B",

    },
    {
        id: "F",
        parent_node: "B",

    },
    {
        id: "G",
        parent_node: "C",

    },
    {
        id: "H",
        parent_node: "C",

    },
    {
        id: "I",
        parent_node: "E",

    },
    {
        id: "J",
        parent_node: "E",

    },
    {
        id: "K",
        parent_node: "G",

    }
]

Let us have an array to store the sub-node ids of the node we wish to find.



let subNodes = []

Get sub-node ids

Let us have a function to get the ids of sub-nodes of a node. It is a recursive function that traverses through the tree to sub-nodes and backtracks when a sub-node with no child is met.



// recursive function to get sub nodes 
function getSubNodes(node) {

    let isParent = false
    for (let j = 0; j < tree.length; j++) {
        if (tree[j].parent_node === node) {
            isParent = true
            break;
        }
    }
    // return if the node is not a parent 
    if (isParent === false) {
        return
    }
    else {
        // find the sub-nodes of the given node 
        // the undefined results are filtered out
        let intermediateNodes = tree.map((eachNode) => {
            if (eachNode.parent_node === eachNode.id) {
                // to cancel self loop
            }
            else if (eachNode.parent_node === node) {
                return eachNode.id
            }
        }).filter(ele => ele !== undefined)
        // spread the results into the subNodes array 
        // with the previous data
        subNodes = [...subNodes, ...intermediateNodes]
        //recursive calling to go into depth
        intermediateNodes.map((item) => { getSubNodes(item) })
    }
    // Set is used to remove duplicates
    subNodes = Array.from(new Set(subNodes))

}

List sub-nodes

Let us have a function to list sub-nodes of a node. This function call getSubNodes(node) to get sub-nodes ids and displays the sub-nodes data.



// function to list sub nodes 
function listSubNodes(node) {
    subNodes = []
    getSubNodes(node)
    console.log(tree.filter(item => subNodes.includes(item.id)))
}

So we can find all the sub-nodes of node "C", by calling the listSubNodes("C") function.



listSubNodes("C")

Output



[
  { id: 'G', parent_node: 'C' },
  { id: 'H', parent_node: 'C' },
  { id: 'K', parent_node: 'G' }
]

This is the logic I used for solving the addressed problem, after analysing the above solution please share your thoughts, and ways to improve it.

Thank you.

Blog

Finding all children of a node in a tree

Bijish O B

Get sub-node ids

List sub-nodes

Output

Join Our Newsletter. No Spam, Only the good stuff.

Related