Finding all children of a node in a tree
Tags: javascript, tree, algorithms
Published: 2022-11-28 17:36:49

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ss4bj94lj1zuefcw3psw.png)

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. 

```javascript
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.

```javascript
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.
```javascript
// 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. 
```javascript
// 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.
```javascript
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.