Find the parent element of an array by the id of its child

Question

I have a JS array that looks like this:

const arr = [
    {
        i: "tooltip_119",
        children: [
            {
                i: "text_345",
                children: []
            },
            {
                i: "wraper_375",
                children: [
                    {
                        i: "grid_15",
                        children: []
                    }
                ]             
            }
        ]
    },
    {
        i: "chart_123",
        children: []
    },
    {
        i: "graph_467",
        children: []
    },
]

The idea is that such an array can potentially have an infinite number of nestings. And I need a function that, taking the i parameter of some element, will return the i parameter of its parent (or 0 if the element is at the root and has no parents). An example of how such a function works:

console.log(findParent(arr, "grid_15"))  // returns "wraper_375"

I wrote a function like this:

export function findParent(arr, i) {   // this func has a bug on deep levels
  for (let j = 0; j < arr.length; j++) {
    const element = arr[j];
    if (element.children && element.children.length > 0) {
      const childElement = element.children.find((e) => e.i === i);
      if (childElement) {
        return element.i;
      } else {
        const parentElement = findParent(element.children, i);
        if (parentElement) {
          return parentElement.i;
        }
      }
    }
  }
  return 0;
}

The problem is that my function doesn't work at deeper levels of nesting. I would be grateful for help
Expected outputs:

findParent(arr, "tooltip_119")  // 0
findParent(arr, "chart_123")  // 0
findParent(arr, "graph_467")  // 0
// 0 is returned because these elems do not have parent elem 

findParent(arr, "text_345")  // "tooltip_119"
findParent(arr, "wraper_375")  // "tooltip_119"

findParent(arr, "grid_15")  // "wraper_375"

Can you provide a few examples of inputs / outputs, some that work as expected and some that don't ? That could help targeting the source of the issue. — Halibut, Aug 11 '23 at 09:00
Can you be more explicit about "doesn't work"? Is there no result? wrong result? throws an error? — Kaddath, Aug 11 '23 at 09:05
One logical error that is quite evident: when you recurse, you expect your function `findParent` to return a parent element, but it actually returns an id. You can try with simply `return findParent(element.children, i);` in your else block — Kaddath, Aug 11 '23 at 09:11
My func used to return undefined on deeper levels. But I think the example of Alexander works perfectly — Listopad02, Aug 11 '23 at 09:16
Yeah, Alexander gave you a fish whereas I was trying to teach you how to fish, as the saying says ;) — Kaddath, Aug 11 '23 at 09:43

Alexander Nenashev · Accepted Answer · 2023-08-15T08:21:34.020

A simple recursion could be like that:

const findParentId = (arr, id, parentId = 0) => {
  for(const {children, i} of arr){
    if(i === id){
      return parentId;
    }
    if(children.length){
      const childId = findParentId(children, id, i);
      if(childId){
        return childId;
      }
    }
  }  
};

['wrong_id', 'tooltip_119', 'wraper_375', 'grid_15', 'second_childs_child', 'graph_467']
    .forEach(id => console.log(id, '=>', findParentId(arr, id)));

<script>
const arr = [
    {
        i: "tooltip_119",
        children: [
            {
                i: "text_345",
                children: []
            },
            {
                i: "wraper_375",
                children: [
                    {
                        i: "grid_15",
                        children: []
                    }
                ]             
            }
        ]
    },
    {
        i: "chart_123",
        children: [{i: 'second_childs_child', children: []}]
    },
    {
        i: "graph_467",
        children: []
    },
]
</script>

Another option would be to use a stack to traverse the object:

const findParentId = (arr, id) => {

    let curr = {parentId: 0, arr, j:0};

    stack: while (curr) {

        let { parentId, arr, j } = curr;

        while (j < arr.length) {
            const { children, i } = arr[j];
            curr.j = ++j;
            if (i === id) {
                return parentId;
            }
            if (children.length) {
                curr = { parentId: i, arr: children, j: 0, parent: curr };
                continue stack;
            }
        }

        curr = curr.parent;

    }
};

['wrong_id', 'tooltip_119', 'wraper_375', 'grid_15', 'second_childs_child', 'graph_467']
    .forEach(id => console.log(id, '=>', findParentId(arr, id)));

<script>
const arr=[{i:"tooltip_119",children:[{i:"text_345",children:[]},{i:"wraper_375",children:[{i:"grid_15",children:[]}]}]},{i:"chart_123",children:[{i:"second_childs_child",children:[]}]},{i:"graph_467",children:[]},];
</script>

And benchmarking:

<script benchmark data-count="1000000">

const arr=[{i:"tooltip_119",children:[{i:"text_345",children:[]},{i:"wraper_375",children:[{i:"grid_15",children:[]}]}]},{i:"chart_123",children:[{i:"second_childs_child",children:[]}]},{i:"graph_467",children:[]},];
const ids = ['wrong_id', 'tooltip_119', 'wraper_375', 'grid_15', 'second_childs_child', 'graph_467'];

// @benchmark Alexander(recursion)

const findParentId = (arr, id, parentId = 0) => {
  for(const {children, i} of arr){
    if(i === id){
      return parentId;
    }
    if(children.length){
      const childId = findParentId(children, id, i);
      if(childId){
        return childId;
      }
    }
  }  
};
// @run
ids.map(id => findParentId(arr, id));

// @benchmark Alexander(stack)

const findParentId2 = (arr, id) => {

    let curr = {parentId: 0, arr, j:0};

    stack: while (curr) {

        let { parentId, arr, j } = curr;

        while (j < arr.length) {
            const { children, i } = arr[j];
            curr.j = ++j;
            if (i === id) {
                return parentId;
            }
            if (children.length) {
                curr = { parentId: i, arr: children, j: 0, parent: curr };
                continue stack;
            }
        }

        curr = curr.parent;

    }
};
// @run
ids.map(id => findParentId2(arr, id));
   
    
</script>
<script src="https://cdn.jsdelivr.net/gh/silentmantra/benchmark/loader.js"></script>

Mulan · Answer 2 · 2023-08-12T16:05:18.013

Here's a unique and efficient solution using a single for loop and a single if -

function find(nodes, childId) {
  return callcc(function run(exit, parent = null, children = nodes) {
    for (const node of children) {
      if (node.i == childId)
        exit(parent) // short-circuit evaluation
      else
        run(exit, node, node.children)
    }
  })
}

console.log(find(arr, "grid_15"))

{
  i: 'wraper_375',
  children: [
    { i: 'grid_15', children: [] },
  ]
}

It depends on generic callcc, details of implementation in this Q&A -

const callcc = f => {
  const box = Symbol()
  try { return f(unbox => { throw {box, unbox} }) }
  catch (e) { if (e?.box == box) return e.unbox; throw e  }
}

If you only want the parent's id, you can exit(parent.i) instead.

Very nice, as always. See my answer for a BFS version. – Scott Sauyet Aug 14 '23 at 19:06 — Scott Sauyet, Aug 14 '23 at 19:06

score 2 · Answer 3 · answered Aug 14 '23 at 19:05

The useful answers from Alexander Nenashev and Aniket Raj, as well as the very interesting continuation-based one from Mulan, all do depth-first traversals to find the first match.

Another technique would be to do a breadth-first traversal. Here we have one built on a more generic parent-finding-by-predicate function, which itself is built atop a generic node-finding-by-predicate function.

const findNode = (pred) => (xs = []) => 
  xs.find(pred) || findNode(pred)(xs.flatMap(x => x.children || []))

const findParent = (pred = () => false) =>
  findNode(({children = []}) => children.some(pred))

const findParentIdById = (xs = [], id = '', p = findParent((x) => x.i == id)(xs)) => 
  p && p.i

const arr = [{i: "tooltip_119", children: [{i: "text_345", children: []}, {i: "wraper_375", children: [{i: "grid_15", children: []}]}]}, {i: "chart_123", children: []}, {i: "graph_467", children: []}]

console.log(findParentIdById(arr, 'grid_15'))

Here findNode and findParent are reusable utility functions which accept a predicate and return function which accept an array. findNode recursively finds the first node which matches the predicate, and if none does, the first of their children which matches it, and if none does, the first of their grand-children, and so on. findParent takes a predicate and calls findNode with a predicate which checks if any of the node's children match the original one.

findParentById simply calls findParent with a predicate which tests if the i property matches the value supplied.

score 1 · Answer 4 · answered Aug 11 '23 at 09:11

For deep nesting, this data representation might not be the most effective. You may consider restructuring it and make your life easier.

Especially if you would have to call this findParent function frequently, it might be worth migrating your array to a different structure, like so:

const arr = [
    { i: "tooltip_119", parent: null },
    { i: "text_345", parent: "tooltip_119" },
    { i: "wraper_375", parent: "tooltip_119" },
    { i: "grid_15", parent: "wraper_375" },
    { i: "chart_123", parent: null },
    { i: "graph_467", parent: null }
];

Then it's just a lookup as compared to a search: O(1) instead of O(N) complexity. Hope this helps.

I have thought of it, but this sollution can not be implemented in my project since i use React-grid-layout and i need my array to be as it is in the example. But it's still an interesting concept — Listopad02, Aug 11 '23 at 09:18

Jerry · Answer 5 · 2023-08-11T10:29:50.277

Here is the working example:
It returns the parent node (with all of its details) of found children element.

const arr = [
  {
    i: "tooltip_119",
    children: [
      {
        i: "text_345",
        children: [],
      },
      {
        i: "wraper_375",
        children: [
          {
            i: "grid_15",
            children: [],
          },
        ],
      },
    ],
  },
  {
    i: "chart_123",
    children: [],
  },
  {
    i: "graph_467",
    children: [
      {
        i: "chart_1222",
        children: [],
      },
    ],
  },
];

//solution: 

function finder(arr, key, parent) {
  for (let elem of arr) {
    if (elem.i == key) return parent;
    if (elem.children.length > 0) {
      let foundParentNode = finder(elem.children, key, elem);
      if (foundParentNode) return foundParentNode;
    }
  }
}

let result = finder(arr, "grid_15", {});

console.log(result.i);

Find the parent element of an array by the id of its child

5 Answers5