JavaScript: Adding recursion result to array and return it

Question

I have a nested object and my goal is to get the path until a key-value pair matches in an array.

My current implementation implements this by strings and concatinating the stringts with da dot (".").

However, instead of that I would like to add all the interim results to the array and push to it. But somehow this does not work.

Code with example Data

const data = [
    {
        parentId: "1111",
        name: "Audi",
        children : [
            {
                parentId: "2222",
                name: "Benz",
                children : [
                    {
                        parentId: "3333",
                        name: "VW",
                        children : [
                        ]
                    }
                ]
            }
        ]
    }
]




const pathTo = (array, target) => {
    var result;
    array.some(({ parentId, name, children = [] }) => {
        if (parentId === target) {
            return result = JSON.stringify({"parentId" : parentId, "name" : name});
        }
        var temp = pathTo(children, target)
        if (temp) {
            return result = JSON.stringify({"parentId" : parentId, "name" : name}) + "." + temp;
        }
    });
    return result;
};


console.log(pathTo(data, "3333"))

Current Result

{"parentId":"1111","name":"Audi"}.{"parentId":"2222","name":"Benz"}.{"parentId":"3333","name":"VW"}

=> The Path concatenated with a string. But I would like :

Expected Result

[ "{"parentId":"1111","name":"Audi"}", "{"parentId":"2222","name":"Benz"}"{"parentId":"3333","name":"VW"}"]

=> an array with all the elements in subsequent order.

Nina Scholz · Accepted Answer · 2021-10-21 08:41:47Z

1

You could return an array or undefined.

const
    data = [{ parentId: "1111", name: "Audi", children : [{ parentId: "2222", name: "Benz", children : [{ parentId: "3333", name: "VW", children : [] }] }] }],
    pathTo = (array, target) => {
        let result;
        array.some(({ parentId, name, children = [] }) => {
            if (parentId === target) {
                result = [{ parentId: parentId, name: name }];
                return true;
            }
            const temp = pathTo(children, target)
            if (temp) {
                result = [{ parentId: parentId, name: name }, ...temp];
                return true;
            }
        });
        return result;
    };

console.log(pathTo(data, "3333"))

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

answered Oct 21, 2021 at 8:41

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

emplo yee Over a year ago

seems to be right, thank you. One question: You are definig the const data, then follows a comma (","), then you add the function name "pathTo" without a "const", "var", or "let". How is this notation called?

Nina Scholz Over a year ago

it is just standard to declare and initialize multiple variables/constants with one statement (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…). it applies as well to var and let (both works without value as well). i do not know, if it has a special name

Scott Sauyet · Accepted Answer · 2021-10-21 14:46:09Z

I prefer to break problems like this into pieces and make at least some of it more generic in the process.

function * traversePaths (xs, path = []) {
  for (let x of xs) {
    const newPath = [...path, x]
    yield newPath
    yield * traversePaths (x .children || [], newPath)
  }
}

const deepFindPath = (pred) => (xs) => {
  for (let path of traversePaths (xs)) {
    if (pred (path [path.length - 1])) {return path} 
  }
}

const pathByParentId = (target) =>
  deepFindPath (({parentId}) => parentId == target)

const data = [{parentId: "1111", name: "Audi", children : [{parentId: "2222", name: "Benz", children : [{parentId: "3333", name: "VW", children : []}]}]}]


// stringified to avoid SO's `/**id:4**/` - `/**ref:4**/,` notation
console .log (JSON .stringify ( 
  pathByParentId ('3333') (data)
, null, 4))

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

Here traversePaths is a generator function that takes any array whose elements have (optional, and recursive) children properties, and traverses it (preorder) yielding a array of object/sub-objects nodes for each path in the array.

deepFindPath returns the path to the first node that matches the predicate supplied.

These two functions are generic. Then to solve your problem we write the simple pathByParentId, which simply accepts a target id and passes to deepFindPath a function which tests if the node's parentId property matches that target id. It will return the path to the first matching node, or undefined if nothing matches.

Your requested output matched the above, except that you didn't mention the children nodes. I prefer this return, just simple references to the existing nodes. But if you really don't want the children, then you can just do:

const pathByParentId = (target) => (
  data, 
  res = deepFindPath (({parentId}) => parentId == target) (data)
) => res && res .map (({children, ...rest}) => rest)

While we could do this in the traversal function, it would make that function less generic and probably less helpful. But if you wanted to do so, you could keep the original version of pathByParentId and replace traversePaths with this:

function * traversePaths (xs, path = []) {
  for (let {children, ...rest} of xs) {
    const newPath = [...path, rest]
    yield newPath
    yield * traversePaths (children || [], newPath)
  }
}

This is less flexible than the previous version, but it still generically lists the paths to any array whose elements have (optional, and recursive) children properties. The elements in those lists are new objects, similar to the original but missing the children properties.

vincent · Accepted Answer · 2022-06-12 19:41:25Z

If you are ok with using a dependency, I'd do that instead. Here is a solution using object-scan.

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

<script type="module">
import objectScan from 'https://cdn.jsdelivr.net/npm/[email protected]/lib/index.min.js';

const data = [{ parentId: '1111', name: 'Audi', children: [{ parentId: '2222', name: 'Benz', children: [{ parentId: '3333', name: 'VW', children: [] }] }] }];

const find = (obj, v) => objectScan(['**'], {
  abort: true,
  filterFn: ({ value }) => value === v,
  rtn: ({ parents }) => parents
    .filter((p) => !Array.isArray(p))
    .reverse()
    .map(({ parentId, name }) => ({ parentId, name }))
})(obj);

console.log(find(data, '3333'));
/* => [
  { parentId: '1111', name: 'Audi' },
  { parentId: '2222', name: 'Benz' },
  { parentId: '3333', name: 'VW' }
] */
</script>

Disclaimer: I'm the author of object-scan

Collectives™ on Stack Overflow

JavaScript: Adding recursion result to array and return it

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related