CODEWITHSUNDEEP
javascriptarraysloopsobjectrecursion
peon123
peon123

Reputation: 398

Nested recursive object loop

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

Upvotes: 1

Views: 366

Answers (3)

Mulan
Mulan

Reputation: 135197

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

Upvotes: 1

Nina Scholz
Nina Scholz

Reputation: 386520

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

Upvotes: 1

Salmin Skenderovic
Salmin Skenderovic

Reputation: 1720

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

Upvotes: 1

Related Questions