Recurvisely Find Children Of Children And Remove

September 08, 2024 Post a Comment

I have an array that has a child of children and everything is related by parentId. example: [ {id: 1, parentid:0},{id: 2, parentid:1}, {id: 3, parentid:2},{id: 4, parentid:2},{id

Solution 1:

Here's a functional way you can do it using recursion. The numbered bullet points match the numbered comments in the code below.

(base) There is no node so there is nothing left to process; return the result r
(induction) There is at least one node. If the node's id or parentid is in the set s, a matching node has been found. Add the node's id to the set and start the search over with the partial result r and the remaining nodes, more.
(induction) There is at least one node and it does not match the ids we are searching for. Append the node to the result and continue searching more nodes.

constremoveFamily =
  ( id = 0
  , [ node, ...more ] = []
  , s = newSet ([ id ])
  , r = []
  ) =>
    node === undefined
      ? r                               // 1
      : s .has (node.id) || s .has (node.parentid)
          ? removeFamily                // 2
              ( id
              , [ ...r, ...more ]
              , s .add (node.id)
              , []
              )
          : removeFamily                // 3
              ( id
              , more
              , s
              , [ ...r, node ]
              )

const nodes =
  [ { id: 1, parentid: 0 }
  , { id: 2, parentid: 1 }
  , { id: 3, parentid: 2 }
  , { id: 4, parentid: 2 }
  , { id: 10, parentid: 4 }
  , { id: 5, parentid: 0 }
  , { id: 6, parentid: 5 }
  , { id: 7, parentid: 7 }
  ]

const newNodes =
  removeFamily (1, nodes)

console .log (newNodes)
// [ { id: 5, parentid: 0 }// , { id: 6, parentid: 5 }// , { id: 7, parentid: 7 }// ]

Here it is rewritten with if statements, if that helps you see it better -

constremoveFamily =
  ( id = 0
  , [ node, ...more ] = []
  , s = newSet ([ id ])
  , r = []
  ) =>
  { if (node === undefined)
      return r               // 1elseif (s .has (node.id) || s .has (node.parentid))
      return removeFamily    // 2
        ( id
        , [ ...r, ...more ]
        , s .add (node.id)
        , []
        )
    elsereturn removeFamily    // 3
       ( id
       , more
       , s
       , [ ...r, node ]
       )
  }

And here's a stack-safe variant that uses a generic loop/recur interface. This version works even when the list of nodes could contain millions of nodes. It also has a slightly better public interface as only two (2) of the parameters are configurable at the call site -

constrecur = (...values) =>
  ({ recur, values })

constloop = f =>
{ let a = f ()
  while (a && a.recur === recur)
    a = f (...a.values)
  return a
}

constremoveFamily = (id = 0, nodes = []) =>
  loop
    ( ( [ node, ...more ] = nodes
      , s = newSet ([ id ])
      , r = [] 
      ) =>
        node === undefined
          ? r                           // 1
          : s .has (node.id) || s .has (node.parentid)
            ? recur                     // 2
                ( [ ...r, ...more ]
                , s .add (node.id)
                , []
                )
            : recur                     // 3
                ( more
                , s
                , [ ...r, node ]
                )
    )

const nodes =
  [ { id: 1, parentid: 0 }
  , { id: 2, parentid: 1 }
  , { id: 3, parentid: 2 }
  , { id: 4, parentid: 2 }
  , { id: 10, parentid: 4 }
  , { id: 5, parentid: 0 }
  , { id: 6, parentid: 5 }
  , { id: 7, parentid: 7 }
  ]


const newNodes =
  removeFamily (1, nodes)

console .log (newNodes)
// [ { id: 5, parentid: 0 }// , { id: 6, parentid: 5 }// , { id: 7, parentid: 7 }// ]

Solution 2:

You could take a Map for the relations and a Generator for getting all id for removing.

function* remove(id) {
    yield id;
    for (id of relations.get(id) || []) yield* remove(id);    
}

var data = [{ id: 1, parentid: 0 }, { id: 2, parentid: 1 }, { id: 3, parentid: 2 }, { id: 4, parentid: 2 }, { id: 10, parentid: 4 }, { id: 5, parentid: 0 }, { id: 6, parentid: 5 }, { id: 7, parentid: 7 }],
    relations = data.reduce((m, { id, parentid }) => m.set(parentid, [...(m.get(parentid) || []), id]), newMap),
    id = 1,
    ids = [...remove(id)],
    i = data.length;
    
while (i--)
    if (ids.includes(data[i].id))
        data.splice(i, 1);

console.log(data);

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

Solution 3:

Summary

You are basically pruning the family tree. The job is complicated by the fact that there is no explicit tree data structure. Instead the tree structure is implied by a set of local parental relationships (the entries of the array that provides you with these relations could be sorted in any order).

You could build a genuine tree structure first, then delete all nodes with .parentid === 1 (staying with your example), eliminating all descendants along. This procedure may be optimized by not building the subtrees whose roots have .parentid === 1.

The following suggestion is simpler. The code repeatedly searches for children of nodes known to be eliminated until no new such children can be found anymore. Therefore it keeps track of currently known descendants in a dictionary.

The simple idea comes at the cost of a O(n^2) worst-case run-time, n being the number of entries in the original array.

The algorithm is an instance of tail recursion and can therefore the recursion can be schematically transformed into a loop.

Note that the [p]bdict_seen dictionary can actually be eliminated, as its update do exactly mirror the updates of the [p]bdict_descendants dictionary.

Running the code (for the given example):

in a browser: Drop it into the console and hit CR.
under node.js: Run 'node <thisfile>.js'

Code

let ao_nodes =  [                                                                      
     {id: 1, parentid:0},{id: 2, parentid:1},                               
     {id: 3, parentid:2},{id: 4, parentid:2},{id: 10, parentid:4},          
     {id: 5, parentid:0},{id: 6, parentid:5},{id: 7, parentid:7}            
    ];                                                                      



    functiondemo_kernel ( pbdict_descendants, pbdict_seen ) {
        let b_foundsome = false
          ;

        ////  For all nodes://     If not yet identified as a descendant and its parent is among the set of known ancestors, add it to the set of descendants.//      for (let o_node of ao_nodes ) {
            if (!pbdict_seen.hasOwnProperty ( o_node.id )) { // using 'pbdict_descendants' for this test is equivalent; in doing so, [p]bdict_seen can be removed from the code altogether.  if (pbdict_descendants.hasOwnProperty ( o_node.parentid )) {
                    b_foundsome = true;
                    pbdict_descendants[o_node.id] = true;
                    pbdict_seen[o_node.id]      = true;
                }
            }
        }
        
        ////  At least 1 new descendant has been found on this level.//  If no more descendants are found, this marks the end of the recursion.//if (b_foundsome) {
            demo_kernel ( pbdict_descendants, pbdict_seen );
        }
    } // demo_kernelfunctiondemo_kernel_nonrec ( pbdict_descendants, pbdict_seen ) {
        let b_foundsome = true
          ;

        ////  For all nodes://     If not yet identified as a descendant and its parent is among the set of known ancestors, add it to the set of descendants.//while (b_foundsome) {
            b_foundsome = false;
            for (let o_node of ao_nodes ) {
                if (!pbdict_seen.hasOwnProperty ( o_node.id )) { // using 'pbdict_descendants' for this test is equivalent; in doing so, [p]bdict_seen can be removed from the code altogether.  if (pbdict_descendants.hasOwnProperty ( o_node.parentid )) {
                        b_foundsome = true;
                        pbdict_descendants[o_node.id] = true;
                        pbdict_seen[o_node.id]      = true;
                    }
                }
            }
        }      
    } // demo_kernel_nonrecfunctiondemo ( ps_id ) {
        let ao_purged
          , bdict_descendants
          , bdict_seen
          ;
        
        //// Register start node//
        bdict_descendants = {
            [ps_id]: true
        };
        bdict_seen = {
            [ps_id]: true
        };
        
        //// identify descendants.//  Express recursion recursion ////  Use either one of the next two lines//      demo_kernel:        recursive (demonstration purpose only)//      demo_kernel_nonrec: non-recursive (use this one)////*** demo_kernel ( bdict_descendants, bdict_seen ); 
        demo_kernel_nonrec ( bdict_descendants, bdict_seen );
        
        ////  Compile result: produce the purged set of nodes. //
        ao_purged = [];
        for (let o_node of ao_nodes ) {
            if (!bdict_descendants.hasOwnProperty ( o_node.id )) {
                ao_purged.push ( o_node );
            }
        }
        
        return ao_purged;    
    }

    let n_root = 1
      ;

    console.log ( `original:\n${JSON.stringify(ao_nodes)}.\n\n` ); 
    console.log ( `purged (root: ${n_root}):\n${JSON.stringify(demo ( n_root ))}.\n` ); // Prints to the browser console.

Solution 4:

What you want is a depth-first (or breadth-first) search. So you use the DFS to find all the child and descendant nodes and then just filter them out once you've found them all.

functionremoveFromID(id) {
    let stack = [], found = [];
    children.forEach(child => {
        if (child.id === id) {
          found.push(child);
          stack.push(child);
    });
    while (stack.length > 0) {
      let current = stack.pop();
      children.forEach(child => {
        if (child.id === current.id) {
          stack.push(child);
          found.push(child);
        }
      });
    }
    children = children.filter(child => found.indexOf(child) <= -1);
}

Solution 5:

With ES6 for recursive depth

Didn't test, but it would be something like this

var dataStore = [{}] // filled in with your datafunctionremoveDataWithRelationships(id) {
     // find root parent to removevar itemToRemoveIndex = dataStore.findIndex(ds => ds.id === id);

     // grab reference to removevar currentReference = dataStore[itemToRemoveIndex]

     // remove current item
     dataStore.splice(itemToRemoveIndex,1);

     // look for children on currentReferencevar childrenToRemove = dataStore.find(ds => ds.parentid === currentReference.id);

     // if there are children, look for parents and run recursive operationif (childrenToRemove) {     
           //recursively call this function to remove all children
          childrenToRemove.forEach(id =>  {
               removeDataWithRelationship(id);
          });
     }
}

JavaScript Programmer Calgary