CODEWITHSUNDEEP
javascriptrecursion
LuMaxIe
LuMaxIe

Reputation: 67

How to find the leaf nodes with recursion in javascript?

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.

Upvotes: 3

Views: 1017

Answers (2)

Scott Sauyet
Scott Sauyet

Reputation: 50797

One approach which is not particularly efficient, but is very simple, is to recursively scan the data for the children of a given id. If there are none, we're at a leaf (assuming the id actually is in the input). If there are children, we just flatMap our function over their ids. It looks like this:

const leafDescendents = (items) => (id) => {
  const children = items .filter (({parentId}) => id == parentId) 
  return children .length == 0 
    ? items .find (({menuId}) => menuId == id) ? [id] : [] 
    : children .map (child => child.menuId) .flatMap (leafDescendents (items))
}

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"}];


['1001', '1008', '1009', '0', '999'] .forEach (
  (id) => console .log (`"${id}":\t${JSON .stringify (leafDescendents (items) (id))}`)
)

The only slightly odd bit is that this:

    ? items .find (({menuId}) => menuId == id) ? [id] : []

looks like it should just be this:

    ? [id]

And it could be, if either

  • (a) you know that the inputs will always be the menuId of one of your items

  • (b) you don't mind that unknown inputs will return their own value, for instance

    leafDescendents (items) ("999") //=> ["999"]

If you don't like that oddity, and you suspect that you might be feeding it missing ids, then keep the line intact. Otherwise, you can use the simpler line.

Upvotes: 2

Amadan
Amadan

Reputation: 198334

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"]

Upvotes: 4

Related Questions