How to traverse a nested array, change siblings and return the mutated array

Question

This is my data structure:


const data = [
  {
    id: 'root',
    name: 'root',
    children: [
      {
        id: 'childA',
        name: 'childA',
        children: []
      },
      {
        id: 'childB',
        name: 'childB',
        children: [
          {
            id: 'childB_A',
            name: 'childB_A',
            children: [
              {
                id: 'childB_A_A',
                name: 'childB_A_A',
                children: []
              },
              {
                id: 'childB_A_B',
                name: 'childB_A_B',
                children: []
              }
            ]
          }
        ]
      }
    ]
  }
]

Now let's say I select childB_A_A , this means the path to it is as follows root > childB > childB_A > childB_A_A or with indexes 0 > 1 > 0 > 0 / root[0].children[1].children[0].children[0]

This is the function I have now.

function findItem(children, indexes, item) {
  if (indexes.length <= 0) {
    return item
  }

  const [currPos] = indexes.splice(0, 1)
  const currItem = children[currPos]

  return findItem(currItem.children, indexes, currItem)
}

This is how I'm calling the function findItem(data, [0, 0]) (selecting childA)

It successfully finds the item I'm searching. But that's not all I need, I also need to remove all children from the siblings of the found item.

So if I now have childB_A_A selected and I select childA then childB's children need to be set to an empty array.

And I either need to mutate in place or return the new structure like this:

const data = [
  {
    id: 'root',
    name: 'root',
    children: [
      {
        id: 'childA',
        name: 'childA',
        children: []
      },
      {
        id: 'childB',
        name: 'childB',
        children: []
      }
    ]
  }
]

I have tried using different approaches like passing the id instead of the indexes path & recursively filtering the children like shown in this StackOverflow answer but it removes the sibling and I want to mutate it.

So yeah essentially what I need to do is:

traverse nested array
find item
change all siblings to have an empty array
return changed nested array

In your example you have removed more than just the siblings of the found node. It is not clear what the criterion is for deletion. — trincot, Jul 25 '22 at 18:18
Yes the example doesn't do exactly what I want it only returns the found node. The criteria to delete the arrays is simple: sibling's children of the selected node must be deleted — rodpadev, Jul 25 '22 at 18:22
Can you perform the siblings logic on the example input and show the desired output? — trincot, Jul 25 '22 at 18:24
@trincot: What else do you see deleted? It looks right to me. — Scott Sauyet, Jul 25 '22 at 18:28
The only sibling of `childB_A_A` is `childB_A_B`. Maybe "sibling" means something different for you than me... Seems there is a description missing of a step that moves focus to the parent of the selected node, making it "uncles" or "aunts". And also the selected node is removed... I will move on. — trincot, Jul 25 '22 at 18:29
@trincot: Somehow I read that we were working with `child_A`, and then that result looked correct. But you're right, this says `childB_A_A`, and it makes no sense. Sorry. — Scott Sauyet, Jul 25 '22 at 18:35
@trincot rethinking the deletion criteria made me think of a solution. thank you! I've posted it below — rodpadev, Jul 25 '22 at 18:57

score 1 · Accepted Answer · answered Jul 26 '22 at 16:19

I think if we break this down into some utility and helper functions, it's fairly straightforward.

We write a private _transform function, which is given the target node and its parent node and recursively builds up a new tree (note: it does not mutate; we're not barbarians, after all!) searching for that parent node as it goes, with different behavior for that node and all others. Once it finds that node, it maps its children choosing to keep the one that matches the target node and to clone the others with empty lists of children.

The public transform function is built on top of this and on top of two utility functions, findById, and findParent, themselves both built on the utility deepFind, which finds a node matching the given predicate in a children-based tree. transform merely finds the target node, uses that to find the parent node, and passes these into the private _transform.

// utility functions
const deepFind = (pred) => ([x, ...xs] = []) => 
  x && (pred (x) ? x : deepFind (pred) (x .children) || deepFind (pred) (xs))

const findById = (id) =>  
  deepFind ((x) => x.id == id)

const findParent = (target) => 
  deepFind ((x => x .children .includes (target)))

// main function
const _transform = (parent, target) => (xs) => 
  xs .map ((x) => ({
    ... x,
    children: x == parent 
      ? x .children .map (c => c == target ? c : {...c, children: []}) 
      : _transform (parent, target) (x .children)
  }))

// public function
const transform = (id, xs, target = findById (id) (xs), parent = findParent (target) (xs)) =>
  _transform (parent, target) (xs) 

// sample data
const data = [{id: 'root', name: 'root', children: [{id: 'childA', name: 'childA', children: []}, {id: 'childB', name: 'childB', children: [{id: 'childB_A', name: 'childB_A', children: [{id: 'childB_A_A', name: 'childB_A_A', children: []}, {id: 'childB_A_B', name: 'childB_A_B', children: []}]}]}]}]

// demo
console .log (transform ('childA', data))

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

Note that there is no error-checking for missing ids, but that shouldn't matter, as in that case, it returns something equivalent to your original tree.

This was written without looking at your answer. If you want to use an array of indices rather than an id, it's only a minor change:

// utility functions
const deepFind = (pred) => ([x, ...xs] = []) => 
  x && (pred (x) ? x : deepFind (pred) (x .children) || deepFind (pred) (xs))

const _findByIndices = (indices) => (xs) =>
  indices .length == 0 ? xs : _findByIndices (indices .slice (1)) (xs .children [indices [0]])

const findByIndices = (indices) => (xs) => _findByIndices (indices) ({children: xs})

const findParent = (target) => 
  deepFind ((x => x .children .includes (target)))

// main function
const _transform = (parent, target) => (xs) => 
  xs .map ((x) => ({
    ... x,
    children: x == parent 
      ? x .children .map (c => c == target ? c : {...c, children: []}) 
      : _transform (parent, target) (x .children)
  }))

// public function
const transform = (indices, xs, target = findByIndices (indices) (xs), parent = findParent (target) (xs)) =>
  _transform (parent, target) (xs) 

// sample data
const data = [{id: 'root', name: 'root', children: [{id: 'childA', name: 'childA', children: []}, {id: 'childB', name: 'childB', children: [{id: 'childB_A', name: 'childB_A', children: [{id: 'childB_A_A', name: 'childB_A_A', children: []}, {id: 'childB_A_B', name: 'childB_A_B', children: []}]}]}]}]

// demo
console .log (transform ([0, 0], data))

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

The utility function deepFind is extremely reusable, and findById and findParent are quite useful functions on their own, and you might find many uses for them. findByIndices is perhaps a little less so, but it might come in handy elsewhere.

I need to reiterate that this does not modify your original array. It does some structural sharing, so some nodes will reference the same object between the two trees, but it is a new structure. If that won't work for you, then you might still do something similar to this mutating the tree, but you'll have to do that part without my help; I'm philosophically opposed to such mutation.

rodpadev · Answer 2 · 2022-07-26T15:38:27.597

UPDATE: This does not work after all

Sometimes the best way of solving a problem is not to try...

I finally figured it out by looking out how the StackOverflow answer I linked was returning the whole nested array and decided to follow a similar approach by mixing .map() and my approach and some straightforward logic.

I commented the code to explain my logic

export function selectAndCleanChildren(items, indexes) {
  let selectedItem = null

  const mapItem = (item, indexes) => {
    // if it's the last index then the selected child
    // is one of the current item's children
    if (indexes.length === 1) {
      selectedItem = item.children[indexes[0]] // set the selected child for easy access

      // loop over all children of the currentItem with .map()
      item.children = item.children.map(item => {
        // If: the child id is the same as the selectedItem.id then return the item unchanged
        if (item.id === selectedItem.id) {
          return item
        }
        // Else: keep the child as it is but set it's children to an empty array
        return { ...item, children: [] }
      })

      // return the new item
      return item
    }

    // remove the first index in-place
    indexes.splice(0, 1)

    // recursively call mapItem by passing the currentItem & rest of the indexes
    return mapItem(item, indexes)
  }

  // map over items & call mapItem and pass the item & indexes
  const cleanChildren = items.map(item => mapItem(item, indexes))

  // return the clean children & selectedChild for ease of access
  return { items: cleanChildren, selectedItem }
}

Stackblitz Snippet

[How do I create a runnable stack snippet?](https://meta.stackoverflow.com/questions/358992) — Scott Sauyet, Jul 25 '22 at 20:31
My point was that you can do it inline here in the answer. :-) — Scott Sauyet, Jul 26 '22 at 12:38
This is not a solution, it won't work for all cases. I give up I'm going to figure out something simpler — rodpadev, Jul 26 '22 at 14:36

How to traverse a nested array, change siblings and return the mutated array

2 Answers2