Home > Back-end >  Simple recursive function to find parent object in nested data not finding parents?
Simple recursive function to find parent object in nested data not finding parents?

Time:04-17

I have a nested data structure, and I want to create a recursive function that, given an object's name parameter, will return the parent object's name paramter.

There are several related questions, however, the answers don't explain why my function getParentName isn't working.

Why is getParentName not working?

const nestedData = {
  name: "parent",
  children: [{ name: "child", children: [{ name: "grandchild" }] }],
};

function getParentName(nested, name) {
  if (nested.children && nested.children.map((d) => d.name).includes(name)) {
    return nested.name;
  } else if (nested.children) {
    nested.children.forEach((child) => {
      return getParentName(child, name);
    });
  }
  return undefined; //if not found
}

//The parent of "grandchild" is "child" - but the function returns undefined
const parentName = getParentName(nestedData, "grandchild");

Why does this function not find the parent?

CodePudding user response:

The problem with your answer is .forEach ignores the return value. There is no return for your else if branch. .forEach is for side effects only. Consider using a generator which makes it easier to express your solution -

function* getParentName({ name, children = [] }, query) {
  for (const child of children)
    if (child.name === query)
      yield name
    else
      yield *getParentName(child, query)
}

const data = {
  name: "parent",
  children: [{ name: "child", children: [{ name: "grandchild" }] }],
}

const [result1] = getParentName(data, "grandchild")
const [result2] = getParentName(data, "foobar")
const [result3] = getParentName(data, "parent")

console.log("result1", result1)
console.log("result2", result2)
console.log("result3", result3)

The answer will be undefined if no matching node is found or if a matched node does not have a parent -

result1 child
result2 undefined
result3 undefined

Notice [] is needed to capture a single result. This is because generators can return 1 or more values. If you do not like this syntax, you can write a generic first function which gets only the first value out of generator -

function first(it) {
  for (const v of it)
    return v
}
const result1 = first(getParentName(data, "grandchild"))
const result2 = first(getParentName(data, "foobar"))
const result3 = first(getParentName(data, "parent"))

The advantages of this approach are numerous. Your attempt uses .map and .includes both of which iterate through children completely. In the other branch, .forEach is used which exhaustively iterates through all children as well. This approach avoids unnecessary .map and .includes but also stops immediately after the first value is read.

  • Related