JavaScript: how to filter deep JSON objects

Question

I have an array of deep JSON objects that look like similarly to this:

var hierarchy = [
  {
    "title": "category 1",
    "children": [
      {"title": "subcategory 1",
        "children": [
          {"id": 1, "title": "name 1"},
          {"id": 2, "title": "name 2"},
          {"id": 3, "title": "name 3"}
        ]
      },
      {"title": "subcategory 2",
        "children": [
          {"id": 1, "title": "name 4"}
        ]
      }
    ]
  },
  {
    "title": "category 2",
    "children": [etc. - shortened for brevity]
  }
];

So basically it is a hierarchy - there are categories which can have subcategories which contain objects with some IDs and names. I also have an array of IDs that are related to the deepest hierarchy level (objects with no children) and I need to filter this set of objects in such a way that only (sub)categories that contain defined objects remain.

So for example if I had an array containing two IDs:

var IDs = [2, 3];

the result would be:

var hierarchy = [
  {
    "title": "category 1",
    "children": [
      {"title": "subcategory 1",
        "children": [
          {"id": 2, "title": "name 2"},
          {"id": 3, "title": "name 3"}
        ]
      }
    ]
  }
];

i.e. the whole, the whole 'category 2' object removed, the whole 'subcategory 2' removed, object with ID '1' removed.

The problem is that the depth of those objects is variable and unknown - some objects have no children, some have children that also have children etc., any subcategory can can itself have a subcategory and I basically need to find object with no children that have defined IDs and keep the whole path to each of them.

Thank you.

Answer 1

Basically, perform a depth first traversal of your tree invoking a callback function on each node. If that node is a leaf node and it's ID appears in your list then clone the branch that leads to that leaf, but don't re-clone any part of the branch that was already cloned.

Once you have constructed the partial and filtered copy of your tree you need to cleanup the original. I mutated the original tree in the process for book-keeping purposes - tracking which branches had already been cloned.

Edit: modified code to filter list of trees instead of just a single tree

var currentPath = [];

function depthFirstTraversal(o, fn) {
    currentPath.push(o);
    if(o.children) {
        for(var i = 0, len = o.children.length; i < len; i++) {
            depthFirstTraversal(o.children[i], fn);
        }
    }
    fn.call(null, o, currentPath);
    currentPath.pop();
}

function shallowCopy(o) {
    var result = {};
    for(var k in o) {
        if(o.hasOwnProperty(k)) {
            result[k] = o[k];
        }
    }
    return result;
}

function copyNode(node) {
    var n = shallowCopy(node);
    if(n.children) { n.children = []; }
    return n;
}

function filterTree(root, ids) {
    root.copied = copyNode(root); // create a copy of root
    var filteredResult = root.copied;

    depthFirstTraversal(root, function(node, branch) {
        // if this is a leaf node _and_ we are looking for its ID
        if( !node.children && ids.indexOf(node.id) !== -1 ) {
            // use the path that the depthFirstTraversal hands us that
            // leads to this leaf.  copy any part of this branch that
            // hasn't been copied, at minimum that will be this leaf
            for(var i = 0, len = branch.length; i < len; i++) {
                if(branch[i].copied) { continue; } // already copied

                branch[i].copied = copyNode(branch[i]);
                // now attach the copy to the new 'parellel' tree we are building
                branch[i-1].copied.children.push(branch[i].copied);
            }
        }
    });

    depthFirstTraversal(root, function(node, branch) {
        delete node.copied; // cleanup the mutation of the original tree
    });

    return filteredResult;
}

function filterTreeList(list, ids) {
    var filteredList = [];
    for(var i = 0, len = list.length; i < len; i++) {
        filteredList.push( filterTree(list[i], ids) );
    }
    return filteredList;
}

var hierarchy = [ /* your data here */ ];
var ids = [1,3];

var filtered = filterTreeList(hierarchy, ids);