How to find the leaf nodes with recursion in javascript?-CodePudding

I'm trying to wrap my head around recursion and like to solve a similar problem like this one: Recursively find all children from parent menu.

The difference between my problem and the one from the example above is that I need the result of the function to be a list of leaf nodes. So if you take the JSON data below and I wanted to know what the leaf nodes of menuId 1001 are, I expect the result to be ["1005", "1007", "1009"]. If I wanted to know what the leaf nodes starting from 1004 are, I expect the result to be ["1007", "1009"]

[
    {"menuId":"1001","depth":"1","parentId":"0"},
    {"menuId":"1002","depth":"1","parentId":"0"},
    {"menuId":"1003","depth":"2","parentId":"1001"},
    {"menuId":"1004","depth":"2","parentId":"1001"},
    {"menuId":"1005","depth":"3","parentId":"1003"}, 
    {"menuId":"1006","depth":"3","parentId":"1004"}, 
    {"menuId":"1007","depth":"4","parentId":"1006"}, 
    {"menuId":"1008","depth":"4","parentId":"1006"}, 
    {"menuId":"1009","depth":"5","parentId":"1008"},
]

I've tried altering the code from the link to solve my problem, but I can't seem to figure it out:

    function getChildren(array, id) {
    return array.reduce((r, { menuId }) => {
        if (array.filter(x => x.parentId === id).length === 0) {
            r.push(menuId);
        } else {
            getChildren(array, menuId)
        }
        return r;
    }, []);

Any advice or help will be appreciated.

CodePudding user response：

EDIT: Reworked because I can't read.

Recursion is not a very efficient approach, given that the data structure you have is linearised. Thus, I first convert the data into an actual tree structure, where recursion can shine.

A wrinkle is that you don't have a proper tree, since the root node is missing. I also assumed you don't want your input data changed, so I cloned your data for a non-destructive approach. Allowing the items data to be changed (adding the children property) instead of copying, and inserting a dummy root node would have considerably simplified the code.

const items = [
    {"menuId":"1001","depth":"1","parentId":"0"},
    {"menuId":"1002","depth":"1","parentId":"0"},
    {"menuId":"1003","depth":"2","parentId":"1001"},
    {"menuId":"1004","depth":"2","parentId":"1001"},
    {"menuId":"1005","depth":"3","parentId":"1003"}, 
    {"menuId":"1006","depth":"3","parentId":"1004"}, 
    {"menuId":"1007","depth":"4","parentId":"1006"}, 
    {"menuId":"1008","depth":"4","parentId":"1006"}, 
    {"menuId":"1009","depth":"5","parentId":"1008"},
];

const tree = {};
function treeify(items) {
  const roots = [];
  const lookup = {};
  for (const item of items) {
    lookup[item.menuId] = { ...item, children: [] };
  }
  for (const item of Object.values(lookup)) {
    if (item.parentId in lookup) {
      lookup[item.parentId].children.push(item);
    } else {
      roots.push(item);
    }
  }
  return roots;
}

function leafNodes(root) {
  if (root.children.length) {
    return root.children.flatMap(leafNodes);
  } else {
    return [root];
  }
}

const roots = treeify(items);
const node1001 = roots.find(item => item.menuId == "1001");
const leafNodesOf1001 = leafNodes(node1001);
console.log(leafNodesOf1001);
console.log(leafNodesOf1001.map(item => item.menuId));
// ["1005", "1007", "1009"]