How to flatten tree structure into array of arrays

Question

Given a structure like this:

var node = { children: [] }

That is to say:

1. It only has children property.
2. No parent property.
3. No nextSibling property.

How to build a flat list of arrays with paths to all the leaf nodes, using a top-down approach:

1. The algorithm doesn't use any helper methods, just plain JavaScript.
2. The algorithm builds the arrays as it traverses the tree from the top.

So here is an example data:

var node = {
  item: 1,
  children: [
    {
      item: 2,
      children: [
        {
          item: 3,
          children: [
            {
              item: 4,
              children: []
            },
            {
              item: 5,
              children: []
            },
            {
              item: 6,
              children: [
                {
                  item: 7,
                  children: []
                },
                {
                  item: 8,
                  children: []
                },
                {
                  item: 9,
                  children: []
                }
              ]
            }
          ]
        },
        {
          item: 10,
          children: [
            {
              item: 11,
              children: []
            },
            {
              item: 12,
              children: [
                {
                  item: 13,
                  children: []
                },
                {
                  item: 14,
                  children: []
                }
              ]
            }
          ]
        }
      ]
    }
  ]
}

And the function should return:

[
  [1, 2, 3, 4],
  [1, 2, 3, 5],
  [1, 2, 3, 6, 7],
  [1, 2, 3, 6, 8],
  [1, 2, 3, 6, 9],
  [1, 2, 10, 11],
  [1, 2, 10, 12, 13],
  [1, 2, 10, 12, 14]
]

My attempt so far has been variations of:

function aggregateNodes(node) {
  var stack = [node]
  var array = []
  while (stack.length) {
    var node = stack.pop()
    array.push(node.item)
    node.children.forEach(function(child){
      stack.push(child)
    })
  }
  return array
}

function aggregateNodesRecursive(node) {
  var array = [node.item]
  node.children.forEach(function(child){
    array.push(child.item)
    child.children.forEach(function(confusedNow){
      array.push(confusedNow.item)
      aggregateNodesRecursive(confusedNow)
    })
  })
  return array
}

Answer 1

A recursive approach would be:

 function traverse(node, path = [], result = []){
     if(!node.children.length)
        result.push(path.concat(node.item));
     for(const child of node.children)
         traverse(child, path.concat(node.item), result);
     return result;
 }

Or some hacky ES6:

const traverse = node => 
  (node.children.length?[]:[[node.item]]).concat(...node.children.map(child => 
     traverse(child).map(arr => 
         [node.item].concat(arr)
      )
  ));

Now calling traverse(node) will return the desired result.

Answer 2

You can create recursive function and first check if current element is array or object and store previous item numbers in one variable.

var node = {"item":1,"children":[{"item":2,"children":[{"item":3,"children":[{"item":4,"children":[]},{"item":5,"children":[]},{"item":6,"children":[{"item":7,"children":[]},{"item":8,"children":[]},{"item":9,"children":[]}]}]},{"item":10,"children":[{"item":11,"children":[]},{"item":12,"children":[{"item":13,"children":[]},{"item":14,"children":[]}]}]}]}]}

const result = []
function flat(data, prev = '') {
  if (Array.isArray(data)) {
    data.forEach(e => flat(e, prev))
  } else {
    prev = prev + (prev.length ? '.' : '') + data.item;
    if (!data.children.length) result.push(prev.split('.').map(Number))
    else flat(data.children, prev)
  }
}

flat(node)
console.log(result)

Answer 3

Here is a solution using object-scan. It's handy for all kinds of data processing - once you wrap your head around it.

// const objectScan = require('object-scan');

const find = (tree) => objectScan(['**.children'], {
  reverse: false,
  filterFn: ({ value, parents, context }) => {
    if (value.length === 0) {
      context.push(
        parents
          .filter((p) => 'item' in p)
          .map(({ item }) => item)
          .reverse()
      );
    }
  }
})(tree, []);

const node = { item: 1, children: [{ item: 2, children: [{ item: 3, children: [{ item: 4, children: [] }, { item: 5, children: [] }, { item: 6, children: [{ item: 7, children: [] }, { item: 8, children: [] }, { item: 9, children: [] }] }] }, { item: 10, children: [{ item: 11, children: [] }, { item: 12, children: [{ item: 13, children: [] }, { item: 14, children: [] }] }] }] }] };

console.log(find(node));
/* =>
  [ [ 1, 2, 3, 4 ],
    [ 1, 2, 3, 5 ],
    [ 1, 2, 3, 6, 7 ],
    [ 1, 2, 3, 6, 8 ],
    [ 1, 2, 3, 6, 9 ],
    [ 1, 2, 10, 11 ],
    [ 1, 2, 10, 12, 13 ],
    [ 1, 2, 10, 12, 14 ] ]
*/

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

<script src="https://bundle.run/[email protected]"></script>

Disclaimer: I'm the author of object-scan

---

Edit: And here is a more efficient solution, in case performance is important

// const objectScan = require('object-scan');

const find = (tree) => objectScan(['**.children'], {
  reverse: false,
  breakFn: ({ isMatch, parent, context: { stack } }) => {
    if (isMatch) {
      stack.push(parent.item);
    }
  },
  filterFn: ({ value: { length }, context: { result, stack } }) => {
    if (length === 0) {
      result.push([...stack]);
    }
    stack.pop();
  }
})(tree, { stack: [], result: [] }).result;

const node = { item: 1, children: [{ item: 2, children: [{ item: 3, children: [{ item: 4, children: [] }, { item: 5, children: [] }, { item: 6, children: [{ item: 7, children: [] }, { item: 8, children: [] }, { item: 9, children: [] }] }] }, { item: 10, children: [{ item: 11, children: [] }, { item: 12, children: [{ item: 13, children: [] }, { item: 14, children: [] }] }] }] }] };

console.log(find(node));
/* =>
  [ [ 1, 2, 3, 4 ],
    [ 1, 2, 3, 5 ],
    [ 1, 2, 3, 6, 7 ],
    [ 1, 2, 3, 6, 8 ],
    [ 1, 2, 3, 6, 9 ],
    [ 1, 2, 10, 11 ],
    [ 1, 2, 10, 12, 13 ],
    [ 1, 2, 10, 12, 14 ] ]
*/

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

<script src="https://bundle.run/[email protected]"></script>

Disclaimer: I'm the author of object-scan

Answer 4

You could take an iterative and recursive approach with a function which looks for children or returns the path the last node.

function flatNodes(node) {
    const iter = temp => ({ item, children = [] }) => children.length
            ? children.forEach(iter(temp.concat(item)))
            : nodes.push(temp.concat(item));

    var nodes = [];
    [node].forEach(iter([]));
    return nodes;
}

var node = { item: 1, children: [{ item: 2, children: [{ item: 3, children: [{ item: 4, children: [] }, { item: 5, children: [] }, { item: 6, children: [{ item: 7, children: [] }, { item: 8, children: [] }, { item: 9, children: [] }] }] }, { item: 10, children: [{ item: 11, children: [] }, { item: 12, children: [{ item: 13, children: [] }, { item: 14, children: [] }] }] }] }] };

console.log(flatNodes(node).map(a => JSON.stringify(a)));

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

Answer 5

The accepted answer above throws when a node does not have a children property.

Edit: I realize that the solution I offer below does not satisfy Lance's task. However, it may be useful for flattening a tree structure into a single array.

If the goal is to just create a flat array of all the nodes' item values, this may be better:

const traverse = (node, flattened = [node.item]) => { 
    node.children?.map((child) => {
        flattened.push(child.item); 
        traverse(child, flattened);
    });
    return flattened;
}

The test:

const tree = {
    item: 'a',
    children: [
        { item: 'b'},
        {
             item: 'c', 
             children: [
                { item: 'd'}
             ]
        }
    ]
};
expect(traverse(tree)).toEqual(['a', 'b', 'c', 'd']);