JavaScript: Adding recursion result to array and return it-CodePudding

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.

CodePudding user response：

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

CodePudding user response：

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.