Bijish O B

Posted on

# 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.