JavaScript recursive function for nested objects in array

Question

I'm trying to implement an algorithm to generate a table with hierarchical headers. These ones can be unlimited nested. An html example of the rendered table markup could be the following:

    <table border=1>
      <thead>
        <tr>
          <th colspan="6">
            Super one
          </th>
          <th colspan="6">
            Super two
          </th>
        </tr>
        <tr>
          <th colspan="3">Head one</th>
          <th colspan="3">Head two</th>
          <th colspan="4">Head three</th>
          <th colspan="2">Head four</th>
        </tr>
        <tr>
          <th>Sub one</th>
          <th>Sub two</th>
          <th>Sub three</th>
          <th>Sub four</th>
          <th>Sub five</th>
          <th>Sub six</th>
          <th>Sub seven</th>
          <th>Sub eight</th>
          <th>Sub nine</th>
          <th>Sub ten</th>
          <th>Sub eleven</th>
          <th>Sub twelve</th>
        </tr>
      </thead>
    </table>  

The configuration of the table should be passed as a JavaScript object in this format:

var columns = [
  {
    label: 'Super one',
    children: [
      {
        label: 'Head one',
        children: [
          {label: 'Sub one'},
          {label: 'Sub two'},
          {label: 'Sub three'}
        ]
      },
      {
        label: 'Head two',
        children: [
          {label: 'Sub four'},
          {label: 'Sub five'},
          {label: 'Sub six'}
        ]
      }
    ]
  },
  {
    label: 'Super two',
    children: [
      {
        label: 'Head three',
        children: [
          {label: 'Sub seven'},
          {label: 'Sub eight'},
          {label: 'Sub nine'},
          {label: 'Sub ten'}
        ]
      },
      {
        label: 'Head four',
        children: [
          {label: 'Sub eleven'},
          {label: 'Sub twelve'}
        ]
      }
    ]
  }
];

Now, let's forget about the html rendering and pay attention only to the algorithm that should iterate over the configuration in order to have a simple 2D array in the format:

var structure = [
  [6, 6],
  [3, 3, 4, 2],
  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]; 

where each entry represents a table row (tr) containing its column definition (td) and the number represents the colspan. How can I implement the algorithm?

Currently I created a recursive function which returns the number of total columns based on the configuration:

function getColumnCount(columns) {
  var count = 0;
  for (var i=0; i<columns.length; i++) {
    var col = columns[i];
    if (col.children && col.children.length > 0) {
      count += getColumnCount(col.children);
    }
    else {
      count++;
    }
  }
  return count;
}

it works as expected, but I'm stuck trying to generate the "structure" array... my current (embarrassing) code attempt is this:

function getStructure(columns) {
  var structure = [[]];
  for (var i=0; i<columns.length; i++) {
    var col = columns[i];
    if (col.children && col.children.length > 0) {
      console.log(col.label, '(with children)');
      schema[structure.length - 1].push(getColumnCount(col.children));
      getStructure(col.children, schema);
    }
    else {
      console.log(col.label, '(orphan)');
      schema[structure.length - 1].push(1);
    }
  }
  return structure; 
}

I'm feeling a real dumb, since I know it should be a relatively easy task, but when it comes to recursive functions my brain seems to refuse to collaborate XD

Can you help me?

Answer 1

The tricky part is to calculate a span, which is the number of leaf nodes under the given node or 1 the node is a leaf itself. This value can be defined recursively as follows:

 numberOfLeaves(node) = if node.children then 
       sum(numberOfLeaves(child) for child in node.children) 
       else 1

The rest is pretty straightforward:

var columns = [
    {
        label: 'Super one',
        children: [
            {
                label: 'Head one',
                children: [
                    {
                        label: 'Sub one',
                        children: [
                            {label: 1},
                            {label: 2},
                        ]
                    },
                    {label: 'Sub two'},
                    {label: 'Sub three'}
                ]
            },
            {
                label: 'Head two',
                children: [
                    {label: 'Sub four'},
                    {label: 'Sub five'},
                    {label: 'Sub six'}
                ]
            }
        ]
    },
    {
        label: 'Super two',
        children: [
            {
                label: 'Head three',
                children: [
                    {label: 'Sub seven'},
                    {label: 'Sub eight'},
                    {label: 'Sub nine'},
                    {label: 'Sub ten'}
                ]
            },
            {
                label: 'Head four',
                children: [
                    {label: 'Sub eleven'},
                    {label: 'Sub twelve'}
                ]
            }
        ]
    }
];

var tab = [];

function calc(nodes, level) {
    tab[level] = tab[level] || [];

    var total = 0;

    nodes.forEach(node => {
        var ccount = 0;
        if ('children' in node) {
            ccount = calc(node.children, level + 1);
        } else {
            ccount = 1;
        }
        tab[level].push({
            label: node.label,
            span: ccount
        });

        total += ccount;
    });

    return total;
}

calc(columns, 0);
console.log(tab);

function makeTable(tab) {
    html = "<table border=1>";
    tab.forEach(row => {
        html += "<tr>";
        row.forEach(cell => {
            html += "<td colspan=" + cell.span + ">" + cell.label + "</td>"
        });
        html += "</tr>"
    })
    return html + "</table>";
}

document.write(makeTable(tab))