Make a recursive function that returns its complete path from each final element of a node

Question

I have a hierarchy of nodes in a checkbox tree and I would like to know how to make a recursive function that returns its complete path from each final element of a node, depending on whether it is selected or not.

Can someone help me?

Data Example:

const data = {
  id: 22,
  selected: true,
  children: [
    {
      id: 4813,
      children: [],
      selected: true,
    },
    {
      id: 4720,
      selected: true,
      children: [
        {
          id: 4838,
          selected: true,
          children: [],
        },
        {
          id: 4839,
          selected: true,
          children: [],
        },
        {
          id: 4840,
          selected: true,
          children: [],
        },
        {
          id: 4841,
          selected: true,
          children: [],
        }
      ],
    },
    {
      id: 4719,
      selected: true,
      children: [
        {
          id: 4272,
          selected: true,
          children: [
            {
              id: 4273,
              selected: true,
              children: [],
            },
            {
              id: 4275,
              selected: false,
              children: [],
            },
            {
              id: 4276,
              selected: true,
              children: [],
            },
            {
              id: 4277,
              selected: false,
              children: [],
            },
            {
              id: 4278,
              selected: true,
              children: [],
            },
            {
              id: 4279,
              selected: false,
              children: [],
            },
          ],
        },
      ],
    },
  ],
};



response = [
    "22/4813",
    "22/4720/4838",
    "22/4720/4839",
    "22/4720/4840",
    "22/4720/4841",
    "22/4719/4272/4273",
    "22/4719/4272/4276",
    "22/4719/4272/4278"
];

Here is my code:

export const getHierarchyNodes = (hierarchy: any) => {
    let idNodes: Array<string> = [];
    const clonedHierarchy = { ...hierarchy };
    // const parentId: number = clonedHierarchy.id;
    // const parentChildren: any = [];

    clonedHierarchy.children.forEach((child: any) => {
        if (child.selected || child.checked) {
            // const childNode: string = `${parentId}`;
            const descendetsNodes = getDescendetsNodes(child);
            console.log("descendents: ", descendetsNodes);
        }
    });

    return idNodes;
};

const getDescendetsNodes = (node: any) => {
    let descendents: any = [];
    const dmaExtractor = (items: any) => {
        items.forEach((child: any) => {
            if (child.selected || child.checked) {
                descendents.push(child);
            }

            if (Array.isArray(child.children)) {
                dmaExtractor(child.children);
            }
        });
    };

    if (Array.isArray(node.children)) {
        descendents.push(node);
        dmaExtractor(node.children);
    }
    console.log("descendents: ", descendents);
    return descendents;
};

score 1 · Accepted Answer · answered Feb 03 '21 at 08:00

This little function should do the trick.

    function getPaths(node, currentPath) {
      // return early if not selected
      if(!node.selected) return [];
      // return path of current node if node does not have children
      if(node.children.length === 0) return [ concatPath(currentPath, node.id) ] ;
      // flat map results of recursive call into a single array
      return node.children
        .flatMap(c => getPaths(c, concatPath(currentPath, node.id)))
    }

    // helper function to concat current path and id
    function concatPath(currentPath, id){
      if(currentPath === '') return id;
      return currentPath + '/' + id;
    }

Call it like this: getPaths(data, '')

score 1 · Answer 2 · answered Feb 03 '21 at 16:28

Here's a simple recursion:

const getPaths = ({id, selected, children = []}) => 
  children .length > 0
    ? children .flatMap (getPaths) .map (p => `${id}/${p}`)
    : selected ? [String(id)] : []

const data = {id: 22, selected: true, children: [{id: 4813, children: [], selected: true}, {id: 4720, selected: true, children: [{id: 4838, selected: true, children: []}, {id: 4839, selected: true, children: []}, {id: 4840, selected: true, children: []}, {id: 4841, selected: true, children: []}]}, {id: 4719, selected: true, children: [{id: 4272, selected: true, children: [{id: 4273, selected: true, children: []}, {id: 4275, selected: false, children: []}, {id: 4276, selected: true, children: []}, {id: 4277, selected: false, children: []}, {id: 4278, selected: true, children: []}, {id: 4279, selected: false, children: []}]}]}]}

console .log (getPaths (data))

The base case is when the node has no children. Then, if it's selected we return an array containing its stringified id. If it's not selected, we return an empty array.

Our recursive case simply collects the results of calling the function on the node's children, and then prepends the current id to each path.

This assumes that you want all the leaf nodes which are selected, regardless of whether their ancestors are selected.

If instead, you only want the ones whose entire ancestry is selected, it's a minor change:

const getPaths = ({id, selected, children = []}) => 
  children .length > 0
    ? selected ? children .flatMap (getPaths) .map (p => `${id}/${p}`) : []
    : selected ? [String(id)] : []

const data = {id: 22, selected: true, children: [{id: 4813, children: [], selected: true}, {id: 4720, selected: true, children: [{id: 4838, selected: true, children: []}, {id: 4839, selected: true, children: []}, {id: 4840, selected: true, children: []}, {id: 4841, selected: true, children: []}]}, {id: 4719, selected: true, children: [{id: 4272, selected: true, children: [{id: 4273, selected: true, children: []}, {id: 4275, selected: false, children: []}, {id: 4276, selected: true, children: []}, {id: 4277, selected: false, children: []}, {id: 4278, selected: true, children: []}, {id: 4279, selected: false, children: []}]}]}]}

// deselecting {id: 4272, ...}
data .children [2] .children [0] .selected = false

console .log (getPaths (data))

nice to show variants for selecting paths based on different criteria :) — Mulan, Feb 03 '21 at 17:59

score 1 · Answer 3 · answered Feb 03 '21 at 17:51

I like the flexibility afforded by generators in this situation. First we make a function that returns all paths of your tree -

function* paths(t, path = [])
{ if (t.children.length)
    for (const c of t.children)
      yield *paths(c, [...path, t])
  else
    yield [...path, t]
}

Now we make another generator to filter out {selected: false} paths -

function* selectedPaths(t)
{ for (const p of paths(t))
    if (p.every(_ => _.selected))
      yield p
}

This inversion of control keeps the traversal code nicely decoupled from your transformation code. We can easily collect the selected paths and create /-separated IDs -

const result =
  Array.from(selectedPaths(data), p => p.map(_ => _.id).join("/"))

[
  "22/4813",
  "22/4720/4838",
  "22/4720/4839",
  "22/4720/4840",
  "22/4720/4841",
  "22/4719/4272/4273",
  "22/4719/4272/4276",
  "22/4719/4272/4278"
]

Expand the snippet below to verify the results in your own browser -

function* paths(t, path = [])
{ if (t.children.length)
    for (const c of t.children)
      yield *paths(c, [...path, t])
  else
    yield [...path, t]
}

function* selectedPaths(t)
{ for (const p of paths(t))
    if (p.every(_ => _.selected))
      yield p
}

const data =
  {id: 22, selected: true, children: [{id: 4813, children: [], selected: true}, {id: 4720, selected: true, children: [{id: 4838, selected: true, children: []}, {id: 4839, selected: true, children: []}, {id: 4840, selected: true, children: []}, {id: 4841, selected: true, children: []}]}, {id: 4719, selected: true, children: [{id: 4272, selected: true, children: [{id: 4273, selected: true, children: []}, {id: 4275, selected: false, children: []}, {id: 4276, selected: true, children: []}, {id: 4277, selected: false, children: []}, {id: 4278, selected: true, children: []}, {id: 4279, selected: false, children: []}]}]}]}

const result =
  Array.from(selectedPaths(data), p => p.map(_ => _.id).join("/"))
  
console.log(result)

... and if the requirement was the other of the possibilities I suggested, we could probably replace `p.every(_ => _.selected)` with `last(p).selected`, for some obvious `last` function. — Scott Sauyet, Feb 03 '21 at 21:22
I really like this technique of describing the path to a leaf as an array of objects. I used a (non-generator) version of it in [a recent answer](https://stackoverflow.com/a/66050740/1243641). This adds consistency to various recursive paths I've used, and is more powerful at the same time. Very nice! — Scott Sauyet, Feb 04 '21 at 17:33
i appreciate the feedback. the added flexibility on the consumer side cannot be overstated. — Mulan, Feb 04 '21 at 17:46

Make a recursive function that returns its complete path from each final element of a node

3 Answers3