DEV Community

Cover image for Finding all children of a node in a tree
Bijish O B
Bijish O B

Posted on

Finding all children of a node in a tree

#javascript #tree #algorithms

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.

Tree representation

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", } ]
Enter fullscreen mode Exit fullscreen mode

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

 let subNodes = []
Enter fullscreen mode Exit fullscreen mode

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)) }
Enter fullscreen mode Exit fullscreen mode

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))) }
Enter fullscreen mode Exit fullscreen mode

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

 listSubNodes("C")
Enter fullscreen mode Exit fullscreen mode

Output 

 [ { id: 'G', parent_node: 'C' }, { id: 'H', parent_node: 'C' }, { id: 'K', parent_node: 'G' } ]
Enter fullscreen mode Exit fullscreen mode

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)