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.
Top comments (0)