how to delete objects by recursion?

Question

I ran into a problem that I don’t know how to correctly compose a recursive function. the logic is such that if you delete an item in the application, then all items whose parentId is equal to the id of the item that decided to delete are deleted, and so on. I hope I explained well, I will be very grateful for the help!

const arr = [
    {title: 'one', id: 1, parentId: null},
    {title: 'two', id: 2, parentId: 1},
    {title: 'three', id: 3, parentId: null},
    {title: 'four', id: 4, parentId: 2},
    {title: 'five', id: 5, parentId: 2},
    {title: 'six', id: 6, parentId: 5},
    {title: 'seven', id: 7, parentId: 3},
]
// if we decide to remove "one", the result will be
[
    {title: 'three', id: 3, parentId: null},
    {title: 'seven', id: 7, parentId: 3},
]

I'm stuck on a version that removes subtasks with only one parentId level

const deleteFunc = (array, value) => {
    array = array.filter(item => item.id !== value);
  const findSubTask = array.filter((item) => item.parentId === value);
  array = array.filter(item => item.id !== findSubTask[0].id);

  const findSecondSubTask = array.find(
    (key) => key.parentId === findSubTask[0].id,
  );

  if (findSecondSubTask) {
    return deleteFunc(array, findSubTask[0].id);
  }
  return array;
};

console.log(deleteFunc(arr, 1));

Write a recursive function that finds all the IDs in the parent chain. Then remove all the elements with IDs in this array. — Barmar
– Barmar, Commented Oct 5, 2022 at 21:26
The example and comment you gave doesn't isn't correct following the logic you stated — otejiri
– otejiri, Commented Oct 5, 2022 at 21:29
@otejiri I think the "result" in this case are the items to be deleted, rather than the items that are left in the arr array — MichaelEr
– MichaelEr, Commented Oct 5, 2022 at 21:33
Why do you think that? If you're deleting 1, you delete 2 because its parent is 1, you delete 4 and 5 because their parents are 2, you delete 5 because its parent is 2, and you delete 6 because its parent is 5. The ones that are left are 3 and 7. @otejiri — Barmar
– Barmar, Commented Oct 5, 2022 at 21:40

Barmar · Accepted Answer · 2022-10-05 22:18:17Z

Get the IDs of all the descendants of the starting element using a recursive function. Then remove them.

const arr = [
    {title: 'one', id: 1, parentId: null},
    {title: 'two', id: 2, parentId: 1},
    {title: 'three', id: 3, parentId: null},
    {title: 'four', id: 4, parentId: 2},
    {title: 'five', id: 5, parentId: 2},
    {title: 'six', id: 6, parentId: 5},
    {title: 'seven', id: 7, parentId: 3},
];

function getDescendantIds(id, arr) {
  let result = [id];
  arr.forEach(el => {
    if (el.parentId == id) {
      result = result.concat(getDescendantIds(el.id, arr));
    }
  });
  return result;
}

function removeTitleAndDescendants(title, arr) {
  let start = arr.find(el => el.title == title);
  if (start) {
    let allIds = new Set(getDescendantIds(start.id, arr));
    return arr.filter(el => !allIds.has(el.id));
  }
  return [...arr];
}

let result = removeTitleAndDescendants("one", arr);
console.log(result);

console.config({
    maxEntries: Infinity
});

MichaelEr · Accepted Answer · 2022-10-05 21:50:30Z

There are definitely a number of approaches to this question. You could go ahead and keep a dictionary that will map parent IDs -> Items, so that you could easily perform what you're triyng to do here in a an efficient manner.

Despite that, if we are looking specifically for a javascript solution, I'd try something along the lines of:

const arr = [
    {title: 'one', id: 1, parentId: null},
    {title: 'two', id: 2, parentId: 1},
    {title: 'three', id: 3, parentId: null},
    {title: 'four', id: 4, parentId: 2},
    {title: 'five', id: 5, parentId: 2},
    {title: 'six', id: 6, parentId: 5},
    {title: 'seven', id: 7, parentId: 3},
]

function deleteFromList(titleToDelete) {
  deletedList = [];
  itemToDeleteIdx = arr.indexOf(i=>i.title === titleToDelete);
  if(itemToDeleteIdx !== -1){
  deletedList.push(arr[itemToDeleteIdx]);
  arr.splice(itemToDeleteIdx, 1);
  return deleteRecursive(deleteRecursive[0].parentId, deletedList);
  } else {
  return [];
  }
}

function deleteRecursive(parentIdToDelete, deletedItemsList){
  itemToDeleteIdx = arr.indexOf(i=>i.parentId === parentIdToDelete);
  if(itemToDeleteIdx !== -1){
    deletedItemsList.push(arr[itemToDeleteIdx]);
    arr.splice(itemToDeleteIdx, 1); 
    return deleteRecursive(parentIdToDelete, deletedItemsList)
  }
  else {
    return deletedItemsList;
  }
}

console.log(deleteFromList('three'))

Obviously it's missing a lot of validations and corner cases, but that's the main flow of things.

Mustafa · Accepted Answer · 2022-10-05 22:03:32Z

1

The function you see below takes an array of item ids you want to delete so at the beginning you give an array with the id of the item you want to delete. then it does two simple tasks: delete items in the passed array, find the ids of all items which has the previous item as their parentId and add them to an array you pass to the next call and so on.

function deleteItems(arrIds) {

  if(arrIds.length === 0) return;

  arr = arr.filter((item) => !arrIds.includes(item.id));
  const newIds = [];
  arr.forEach((item) => {
    if(arrIds.includes(item.parentId)) newIds.push(item.id);
  })
  deleteItems(newIds);
};

deleteItems([1]);

answered Oct 5, 2022 at 22:03

Mustafa

3533 silver badges11 bronze badges

Comments

IT goldman · Accepted Answer · 2022-10-05 22:05:42Z

1

Let's convert to a tree:

const arr = [
    {title: 'one', id: 1, parentId: null},
    {title: 'two', id: 2, parentId: 1},
    {title: 'three', id: 3, parentId: null},
    {title: 'four', id: 4, parentId: 2},
    {title: 'five', id: 5, parentId: 2},
    {title: 'six', id: 6, parentId: 5},
    {title: 'seven', id: 7, parentId: 3},
];

var grouped = arr.reduce(function(agg, item) {
  agg[item.id] = item
  return agg;
}, {})

arr.forEach(function(item) {
  if (item.parentId) {
    grouped[item.parentId].children ??= []
    grouped[item.parentId].children.push(item.id)
  }
})

// this is our tree
console.log(grouped)

// now we can:
function get_children_deep(tree, id) {
  var result = [];
  function iterate(tree, id) {
    var obj = tree[id];
    (obj.children || []).forEach(function(child_id) {
      result.push(child_id);
      iterate(tree, child_id);
    })
  }
  iterate(tree, id)
  return result;
}


console.log("all descendants of 1: " + get_children_deep(grouped, 1))

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

So based on that, here's the solution of deleting item and children by title. recursively.

const arr = [
    {title: 'one', id: 1, parentId: null},
    {title: 'two', id: 2, parentId: 1},
    {title: 'three', id: 3, parentId: null},
    {title: 'four', id: 4, parentId: 2},
    {title: 'five', id: 5, parentId: 2},
    {title: 'six', id: 6, parentId: 5},
    {title: 'seven', id: 7, parentId: 3},
];

console.log(delete_by_title(arr, "one"));


function delete_by_title(arr, title) {

  var grouped = arr.reduce(function(agg, item) {
    agg[item.id] = item
    return agg;
  }, {})

  arr.forEach(function(item) {
    if (item.parentId) {
      grouped[item.parentId].children ??= []
      grouped[item.parentId].children.push(item.id)
    }
  })


  function get_children_deep(tree, id) {
    var result = [];

    function iterate(tree, id) {
      var obj = tree[id];
      (obj.children || []).forEach(function(child_id) {
        result.push(child_id);
        iterate(tree, child_id);
      })
    }
    iterate(tree, id)
    return result;
  }

  function id_by_title(arr, title) {
    return arr.find(function(item) {
      return item.title == title
    }).id;
  }

  var id = id_by_title(arr, title)
  var to_delete = get_children_deep(grouped, id)
  to_delete.push(id)

  to_delete.forEach(function(id) {
    delete grouped[id]
  })

  return Object.values(grouped);
}

edited Oct 5, 2022 at 22:05

answered Oct 5, 2022 at 21:41

IT goldman

20.4k2 gold badges18 silver badges34 bronze badges

3 Comments

vinograd Over a year ago

In my case, this solution does not work :(

otejiri Over a year ago

check on the answer I gave, it should do the trick @vinograd

IT goldman Over a year ago

This answer is more of a demonstration of grouping into a tree then doing recursive stuff with it. Easily adaptable.

otejiri · Accepted Answer · 2022-10-05 22:04:51Z

0

if you want to return them then the below should do the trick

const arr = [
    {title: 'one', id: 1, parentId: null},
    {title: 'two', id: 2, parentId: 1},
    {title: 'three', id: 3, parentId: null},
    {title: 'four', id: 4, parentId: 2},
    {title: 'five', id: 5, parentId: 2},
    {title: 'six', id: 6, parentId: 5},
    {title: 'seven', id: 7, parentId: 3},
]

const deleteId = (val) => {
const resultArray = [];
const index = arr.findIndex((n) => n.id === val);
for(let i =0; i < arr.length; i++)
{
  if(arr[i].id === val || arr[i].parentId === arr[index].id)
  {
  resultArray.push(arr[i]);
  }
}
return resultArray;
}

const result = deleteId(1);

console.log(result);

edited Oct 5, 2022 at 22:04

answered Oct 5, 2022 at 21:47

otejiri

9977 silver badges20 bronze badges

5 Comments

k.tten Over a year ago

They want to remove these from the original list.

otejiri Over a year ago

I think op wants them deleted if they match and not the other way round @caTS

Rylee Over a year ago

Your solution returns all that match - they want those deleted instead.

otejiri Over a year ago

I edited to have both solutions @Rylee

Rylee Over a year ago

Try using your solution by deleting "one", it's not recursive. You still end up with elements that should not be there.

k.tten · Accepted Answer · 2022-10-05 22:20:55Z

Essentially the same idea as @Barmar, but done in a different way :)

const arr = [
    {title: 'one', id: 1, parentId: null},
    {title: 'two', id: 2, parentId: 1},
    {title: 'three', id: 3, parentId: null},
    {title: 'four', id: 4, parentId: 2},
    {title: 'five', id: 5, parentId: 2},
    {title: 'six', id: 6, parentId: 5},
    {title: 'seven', id: 7, parentId: 3},
];

function cascadingDelete(arr, title) {
    const index = arr.findIndex((e) => e.title === title);
    
    const indices = [index].concat((function walk(parentId) {
        const children = arr.filter((e) => e.parentId === parentId);
        const indices = children.map((c) => arr.indexOf(c));
        return indices.concat(children.map((c) => walk(c.id)));
    })(arr[index].id)).flat(Infinity);
    
    return arr.filter((_, i) => !indices.includes(i));
}

console.log(cascadingDelete(arr, "one"));

Collectives™ on Stack Overflow

how to delete objects by recursion?

6 Answers 6

Comments

Comments

Comments

3 Comments

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Comments

Comments

Comments

3 Comments

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related