Recurvisely find children of children and remove

Question

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: 10, parentid:4},
{id: 5, parentid:0},{id: 6, parentid:5},{id: 7, parentid:7}
]

I want to remove the object with Id:1 and all it related children. so that would be these objects

{id: 1, parentid:0},{id: 2, parentid:1},
{id: 3, parentid:2},{id: 4, parentid:2},{id: 10, parentid:4}

Answer 1

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}            
    ];                                                                      



    function demo_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_kernel

    function demo_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_nonrec


    function demo ( 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.

Answer 2

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

1. (base) There is no node so there is nothing left to process; return the result r
2. (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.
3. (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.

const removeFamily =
  ( id = 0
  , [ node, ...more ] = []
  , s = new Set ([ 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 -

const removeFamily =
  ( id = 0
  , [ node, ...more ] = []
  , s = new Set ([ id ])
  , r = []
  ) =>
  { if (node === undefined)
      return r               // 1
    else if (s .has (node.id) || s .has (node.parentid))
      return removeFamily    // 2
        ( id
        , [ ...r, ...more ]
        , s .add (node.id)
        , []
        )
    else
      return 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 -

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

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

const removeFamily = (id = 0, nodes = []) =>
  loop
    ( ( [ node, ...more ] = nodes
      , s = new Set ([ 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 }
// ]

Answer 3

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]), new Map),
    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; }

Answer 4

This solution is not dependent on the beginning array's sort order. i.e. grandchildren can be found in the beginning of the array.

Explanations are in the code (array rewritten to have granchildren in front):

// this array is rewritten so granchildren appear first!
let arr = [ 
    {id: 3, parentid:2},{id: 4, parentid:2},{id: 10, parentid:4},
    {id: 5, parentid:0},{id: 6, parentid:5},{id: 7, parentid:7},
    {id: 1, parentid:0},{id: 2, parentid:1}
]

function remove(id, arr) {
    //first time it's called id is put into an array
    let del = (Array.isArray(id))? id: [id]

    let newArr = []

    arr.forEach((obj) => {
        switch (true) {
            // removes topmost parent
            case del.includes(obj.id):
                break;
            // removes subsequent children
            case del.includes(obj.parentid):
                del.push(obj.id)
                break;
            // retains the rest
            default:
                newArr.push(obj)
        }
    })

    // if this pass did remove something, we call function again 
    // since original array may not be sorted and deep grandchildren
    // are found in the beginning of the array
    if (arr.length !== newArr.length) {newArr = remove(del, newArr)}

    // when no further changes are made, we return the result
    return newArr
}

console.log(remove(1, arr)) //results in [{id:5,parentid:0}, {id:6,parentid:5},{id:7,parentid:7}

Answer 5

With ES6 for recursive depth

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

var dataStore = [{}] // filled in with your data

function removeDataWithRelationships(id) {
     // find root parent to remove
     var itemToRemoveIndex = dataStore.findIndex(ds => ds.id === id);

     // grab reference to remove
     var currentReference = dataStore[itemToRemoveIndex]

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

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

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

Answer 6

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.

function removeFromID(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);
}