Javascript - recursively remove nodes of a certain type from tree, but reattach and spread eligible children

Question

I'm writing a recursive function on a JSON tree {name, type, [children]} to remove nodes of a certain type. However, the children of the removed node should get re-attached to the parent, if they are not of the type to be removed.

I'm experiencing the following difficulty: Let's say I want to remove type b on the following tree:

const sampleData = [{
name: "parent",
type: "a",
children: [{
    name: "childA",
    type: "a",
    children: null
    },{
    name: "childB",
    type: "b",
    children: [{
        name: "grandChildA",
        type: "a",
        children: null
        },{
        name: "grandChildB",
        type: "a",
        children: null
        }]
    },{
    name: "childC",
    type: "a",
    children: null
    }]
}]

The original children for parent is [childA, childB, childC]. After the removal, the parent should have children [childA, grandChildA, grandChildB, childC]. However, the result I'm getting is [childA, [grandChildA, grandChildB], childC].

I know I need to spread it out, but I'm not sure where to do it in the recusion.

Here's the function that I have right now (I know I'm using the spread syntax in the wrong place):

const removeType = (node, type) => {
    //if the node should not be removed    
    if (node.type !== type){
        //if the node has children, recursively call to prune children
        if (node.children && node.children.length > 0){
            node.children = [...node.children.map(child => removeType(child, type))
                                             .filter(child => child !== null)]
            return node
        }
        //if the node has no children, return the node
        else return node
    }
    //if the node should be removed
    else if (node.type === type){
        //if the node has children, recursively call, then reattach the children
        if (node.children && node.children.length > 0){
            node.children = [...node.children.map(child => removeType(child, type))
                                             .filter(child => child !== null)]
            return node.children
        }
        //
        else return null
    }
}

Abdel P. · Accepted Answer · 2020-09-06T03:06:45.417

Updated

I think you can use reduce for that, I'm not having my computer right now to test it, but it'll be something like this

const removeType = (node, type) => {
   if (node === null) {
     return null;
   } else {
    return node.reduce((acc, child) => {
      if(child["type"] === type) {
        const removedChild = removeType(child["children"], type);
        acc = [...acc, ...removedChild];
      } else {
        child.children = removeType(child["children"], type);
        acc.push(child);
      }
      return acc;
    }, []);
  }
}

2nd Update

Code reduced:

const removeType = (node, type) => {
    if (!node) return;

    return node.reduce((acc, child) => {
        if(child["type"] === type) {
            const removedChild = removeType(child["children"], type);
            acc = [...acc, ...removedChild];
        } else {
            child.children = removeType(child["children"], type);
            acc.push(child);
        }
        return acc;
    }, []);

}

This returns `[childA, [grandChildA, grandChildB], childC]`, still has the nested array. — Samson Liu, Sep 06 '20 at 00:43

score 2 · Answer 2 · answered Sep 07 '20 at 20:50

I think this answer is just enough different from the others supplied to add it as an alternative. It has the same recursive structure as the answer from Thankyou, but it makes the simplifying assumption that your input is always an array, as are all non-nil children nodes.

const removeType = (node, target) =>
  node .flatMap (({type, children, ...rest}) =>
    type === target
      ? children ? removeType (children, target) : []
      : [{...rest, type, children: children && (removeType (children, target))}]
  )

const sampleData = [{name: "parent", type: "a", children: [{name: "childA", type: "a", children: null},{name: "childB", type: "b", children: [{name: "grandChildA", type: "a", children: null},{name: "grandChildB", type: "a", children: null}]}, {name: "childC", type: "a", children: null}]}]

console .log (
 removeType (sampleData, 'b')
)

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

I'm not claiming this as an improvement on the other answers, but it is an interesting alternative.

Mulan · Answer 3 · 2020-09-06T14:47:34.863

Here's a way to simplify the program using Array.prototype.flatMap, some mathematical induction, and a dash of mutual recursion -

removeType accepts an array of nodes and a query type to remove, q
removeType1 accepts a single node and a query type to remove, q

const removeType = (nodes, q) =>
  (nodes || []).flatMap(n => removeType1(n, q))  // <-- removeType1

const removeType1 = (node, q) =>
  q === node.type
    ? removeType(node.children)                  // <-- removeType
    : { ...node, children: removeType(node.children, q) } // <-- removeType

const input = 
  [{name:"parent",type:"a",children:[{name:"childA",type:"a",children:null},{name:"childB",type:"b",children:[{name:"grandChildA",type:"a",children:null},{name:"grandChildB",type:"a",children:null}]},{name:"childC",type:"a",children:null}]}]
  
const result =
  removeType(input, "b")

console.log(result)

Output -

[
  {
    "name": "parent",
    "type": "a",
    "children": [
      {
        "name": "childA",
        "type": "a",
        "children": []
      },
      {
        "name": "grandChildA",
        "type": "a",
        "children": []
      },
      {
        "name": "grandChildB",
        "type": "a",
        "children": []
      },
      {
        "name": "childC",
        "type": "a",
        "children": []
      }
    ]
  }
]

Note that result is a new object and that input is not mutated as a result of calling removeType.

Mutual recursion is a nice fit for the problem above, but what if you truly wanted just one function?

const removeType = (t, q) =>
  Array.isArray(t)                             // <-- array
    ? t.flatMap(node => removeType(node, q))
: Object(t) === t                              // <-- object (node)
    ? q === t.type
        ? removeType(t.children, q)
        : { ...t, children: removeType(t.children, q) }
: t                                            // <-- else (no operation)

const input = 
  [{name:"parent",type:"a",children:[{name:"childA",type:"a",children:null},{name:"childB",type:"b",children:[{name:"grandChildA",type:"a",children:null},{name:"grandChildB",type:"a",children:null}]},{name:"childC",type:"a",children:null}]}]
  
const result =
  removeType(input, "b")

console.log(result)

Output is mostly the same except notice how this one preserves children: null. Our original program yields the more correct children: [] -

[
  {
    "name": "parent",
    "type": "a",
    "children": [
      {
        "name": "childA",
        "type": "a",
        "children": null
      },
      {
        "name": "grandChildA",
        "type": "a",
        "children": null
      },
      {
        "name": "grandChildB",
        "type": "a",
        "children": null
      },
      {
        "name": "childC",
        "type": "a",
        "children": null
      }
    ]
  }
]

Javascript - recursively remove nodes of a certain type from tree, but reattach and spread eligible children

3 Answers3

Linked