Nested recursive object loop

Question

I have arrays of objects that can also have arrays of their own. My main goal is to find an object with a given id in the whole tree and get readmap to that element by displaying the names of the objects names where it occurs.

For example I have data object like this:

{
  id: '0',
  name: "Boys"
  children: [
   {
    name: "Soldiers",
    children: [
     {
       name: "Bravo"
       children: [
         {name: "Tom"},
         {name: "Andrew"}
       ]
     }
    ]
   },
   {
    name: "Runners",
    children: [
     {
       name: "Team B"
       children: [
         {name: "Mark"},
         {name: "David"}
       ]
     }
    ]
   }
  ]
}

I am currently finding an item by a function

 function findByName (name, array) {
    for (const node of array) {
      if (node.name === name) return node;
      if (node.children) {
        const child = findByName(name, node.children);
        if (child) return child;
      }
    }
  }

But to achive my goal I need also roadmap to that value. For example.

When I want to find "Tom". Besides results of findByName I would like to get {name: "Tom", road: ["Boys", "Soldiers", "Bravo"]

Reopened. The [suggested duplicate](https://stackoverflow.com/q/25403781) has a different structure, with descendants as Object properties rather than the `children` array. — Scott Sauyet, Feb 17 '21 at 14:02

score 1 · Answer 1 · answered Feb 16 '21 at 21:06

You would need to pass down another property which handles the path. Start by defining path as an empty array. And since you only care about the name, you can push the name into this array everytime you find a node that has children.

Then you just keep passing the updated array to your recursive function. See my working example below:

(I updated your function to return an object which contains both the result and path)

function findByName(name, array, path = []) {
  for (const node of array) {
    if (node.name === name) return {result: node, path};
    if (node.children) {
      path.push(node.name) // We update the path with the current node name that has children
      const child = findByName(name, node.children, path );
      if (child) return { result: child, path};
    }
  }
}

Demo: https://jsitor.com/VnktoLq49

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

You could add the path for every leve in the calling function without handing over the path.

const
    findByName = (array, name) => {
        for (const node of array) {
            if (node.name === name) return { ...node, path: [] };
            if (node.children) {
                const child = findByName(node.children, name);
                if (child) return { ...child, path: [node.name, ...child.path] };
            }
        }
    },
    data = [{ id: '0', name: "Boys", children: [{ name: "Soldiers", children: [{ name: "Bravo", children: [{ name: "Tom" }, { name: "Andrew" }] }] }, { name: "Runners", children: [{ name: "Team B", children: [{ name: "Mark" }, { name: "David" }] }] }] }];

console.log(findByName(data, 'Tom'));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Mulan · Answer 3 · 2021-02-17T18:03:24.090

I like generators for this kind or problem because it allows you to select one, many, or all results. Additionally generators give control to the caller, allowing you to stop searching whenever you are satisfied with the result. This can be accomplished with a single function -

function* select(a = [], query = Boolean, path = [])
{ for (const t of a)
  { if (query(t)) yield { ...t, path }
    yield *select(t.children, query, [...path, t.name])
  }
}

const data =
  [{ id: '0', name: "Boys", children: [{ name: "Soldiers", children: [{ name: "Bravo", children: [{ name: "Tom" }, { name: "Andrew" }] }] }, { name: "Runners", children: [{ name: "Team B", children: [{ name: "Mark" }, { name: "David" }] }] }] }]

// select "Tom" OR "Mark"
for (const r of select(data, v => v.name == 'Tom' || v.name == "Mark"))
  console.log("found:", r)

found: {
  "name": "Tom",
  "path": [
    "Boys",
    "Soldiers",
    "Bravo"
  ]
}
found: {
  "name": "Mark",
  "path": [
    "Boys",
    "Runners",
    "Team B"
  ]
}

If you want only the first result, we can use return or break, and searching stops immediately, potentially saving many wasted computations -

function first (it)
{ for (const x of it)
    return x              // <- return and stop searching
}

first(select(data, v => v.name == "Andrew"))

{
  "name": "Andrew",
  "path": [
    "Boys",
    "Soldiers",
    "Bravo"
  ]
}

If you want all of the results, we can use Array.from. Because select is flexible, it allows us to do all sorts of useful queries -

Array.from(select(data, v => !v.children), r => r.name)

[
  "Tom",
  "Andrew",
  "Mark",
  "David"
]

I knew there was a good reason to reopen this! I wrote several different answers, none which seemed to offer anything great, so I didn't post them. I'm entirely unsurprised to have you come through with an elegant answer! One quibble: the name `find` to me is too tied to `Array.prototype.find` with its short-circuiting return. Something like `select`, `query`, or `match` strikes me as clearer. I especially like `select`. — Scott Sauyet, Feb 17 '21 at 17:27
I'm delighted to make a valuable contribution ^_^ I also like `select`, updating the answer now — Mulan, Feb 17 '21 at 17:31

Nested recursive object loop

3 Answers3

Linked