CODEWITHSUNDEEP
javascriptalgorithm
reactor
reactor

Reputation: 1931

create a pruned copy of tree in javascript

I'm trying to create a pruned version of the tree below where I have the source data/tree:

const treeData = [{
  title: '0-0',
  key: '0-0',
  children: [{
    title: '0-0-0',
    key: '0-0-0',
    children: [
      { title: '0-0-0-0', key: '0-0-0-0', children: [] },
      { title: '0-0-0-1', key: '0-0-0-1', children: [] },
      { title: '0-0-0-2', key: '0-0-0-2', children: [] },
    ],
  }, {
    title: '0-0-1',
    key: '0-0-1',
    children: [
      { title: '0-0-1-0', key: '0-0-1-0', children: [] },
      { title: '0-0-1-1', key: '0-0-1-1', children: [] },
      { title: '0-0-1-2', key: '0-0-1-2', children: [] },
    ],
  }, {
    title: '0-0-2',
    key: '0-0-2',
    children: []
  }],
}, {
  title: '0-1',
  key: '0-1',
  children: [
    { title: '0-1-0-0', key: '0-1-0-0', children: [] },
    { title: '0-1-0-1', key: '0-1-0-1', children: [] },
    { title: '0-1-0-2', key: '0-1-0-2', children: [] },
  ],
}, {
  title: '0-2',
  key: '0-2',
  children: []
}];

and an array of leaf nodes as inputs.

const leafNodes = ['0-0-1-2', '0-1-0-1', '0-1-0-2']

Given this input, I would want this pruned tree that uses the leaf nodes to build all paths from the root to each leaf:

const pruned [{
  title: '0-0',
  key: '0-0',
  children: [{
    title: '0-0-1',
    key: '0-0-1',
    children: [
      { title: '0-0-1-2',
        key: '0-0-1-2',
        children: []
      }
    ]
  }]
  }, {
  title: '0-1',
  key: '0-1',
  children: [{
    title: '0-1-0-1',
    key: '0-1-0-1',
    children: []
  }, {
    title: '0-1-0-2',
    key: '0-1-0-2',
    children: []
  }]
}]

I was thinking of building the copy node by node instead of copying the data source and then taking away the paths not buildable based on the array/list of leaf nodes as I figured that would be the easiest to grok for maintainability purposes but even then, I'm puzzled as to how to coordinate the process, especially when accounting for the middle nodes that have already been added to my copy tree in progress as would be the case for '0-1-0-1' and '0-1-0-2'. At any rate, I've been stumped for awhile and threw my hands up. The code referenced is javascript but I'd be open to answers in other languages similar enough to javascript.

Upvotes: 4

Views: 630

Answers (1)

Nina Scholz
Nina Scholz

Reputation: 386736

You could build new array/objects by finding the target key and collect all objects to it by returning the arrays with the necessary nodes.

function getParts(array, leafes) {
    var result = [];
    array.forEach(o => {
        var children;
        if (leafes.includes(o.key)) {
            result.push(o);
            return;
        }
        children = getParts(o.children, leafes);
        if (children.length) {
            result.push(Object.assign({}, o, { children }));                    
        }
    });
    return result;
}

const
    treeData = [{ title: '0-0', key: '0-0', children: [{ title: '0-0-0', key: '0-0-0', children: [{ title: '0-0-0-0', key: '0-0-0-0', children: [] }, { title: '0-0-0-1', key: '0-0-0-1', children: [] }, { title: '0-0-0-2', key: '0-0-0-2', children: [] }] }, { title: '0-0-1', key: '0-0-1', children: [{ title: '0-0-1-0', key: '0-0-1-0', children: [] }, { title: '0-0-1-1', key: '0-0-1-1', children: [] }, { title: '0-0-1-2', key: '0-0-1-2', children: [] }] }, { title: '0-0-2', key: '0-0-2', children: [] }] }, { title: '0-1', key: '0-1', children: [{ title: '0-1-0-0', key: '0-1-0-0', children: [] }, { title: '0-1-0-1', key: '0-1-0-1', children: [] }, { title: '0-1-0-2', key: '0-1-0-2', children: [] }] }, { title: '0-2', key: '0-2', children: [] }],
    leafNodes = ['0-0-1-2', '0-1-0-1', '0-1-0-2'],
    pruned = getParts(treeData, leafNodes);

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

Upvotes: 3

Related Questions