CODEWITHSUNDEEP
javascriptrecursionnested
NicoWheat
NicoWheat

Reputation: 2461

Simple recursive function to find parent object in nested data not finding parents?

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?

Upvotes: 2

Views: 1758

Answers (2)

NicoWheat
NicoWheat

Reputation: 2461

@Mulan answered my question, stating that the function failed because return statements inside .forEach() are ignored. They then offered a generator function as a superior alternative.

For the sake of clarity of comparison, here is a minimally altered form of the original function that works. forEach() was replaced with a (for x of array) loop. In addition only truthy values are returned.


function getParentName(nested, name) {
  if (nested.children && nested.children.some((d) => d.name === id)) {
    return nested.name;
  } else if (nested.children) {
    for (const child of node.children) {
      const result = getParentName(child, id);
      if (result) return result;
    }
  }
  return undefined; //if not found
}

Upvotes: 0

Mulan
Mulan

Reputation: 135406

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.

Upvotes: 4

Related Questions