How to convert an array of integers to a tree?

Question

Here is 100 numbers, 10 per row.

[1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0]

I would like to arrange these numbers into a tree sort of thing, where each node has max 5 elements. Something like this:

[                                                                                       ]
 [                   ],[                   ],[                   ],[                   ]
  [ ],[ ],[ ],[ ],[ ]   [ ],[ ],[ ],[ ],[ ]   [ ],[ ],[ ],[ ],[ ]   [ ],[ ],[ ],[ ],[ ]
   1   6   1   6   1     6   1   6   1   6     1   6   1   6   1     6   1   6   1   6
   2   7   2   7   2     7   2   7   2   7     2   7   2   7   2     7   2   7   2   7
   3   8   3   8   3     8   3   8   3   8     3   8   3   8   3     8   3   8   3   8
   4   9   4   9   4     9   4   9   4   9     4   9   4   9   4     9   4   9   4   9
   5   0   5   0   5     0   5   0   5   0     5   0   5   0   5     0   5   0   5   0

So we have 4 "layers" in the tree:

In layer 1 (top layer), we have 4 children (4 arrays of arrays of numbers).
In layer 2, we have 5 children (5 arrays of numbers).
In layer 3, we have 5 children (5 numbers).
Layer 4 are the numbers.

How does one write a JavaScript algorithm to generate a tree like this? The rules are, max 5 per block. Or more generally, max n per block.

This is somewhat similar to an array chunking algorithm, but at the same time way more complicated it seems.

I have been stumped on this for a few days, but it will help in solving this problem: How to divide an array into a tree of buckets sized by powers of two?

Basically, as the array gets longer, the nesting will get bigger and bigger.

Another simpler example is this, 13-item-array:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3]

Which is converted into this tree:

[           ]
 [ ],[ ],[ ]
  1   6   1
  2   7   2
  3   8   3
  4   9   
  5   0

Hello Lance Pollard! I can't speak for the downvoters, but one thing that strikes me when reading your question is the absence of specifications/requirements regarding which numbers to put in which bin. Does the 2-dimensional structure of the original array matter, or would it be the same if we had a big bag of 100 unordered numbers? — Stef, Sep 18 '20 at 12:44
A quite simple algorithm if you have no requirements: 1) Put the numbers in bins 5 by 5; 2) Put the bins in bins-of-bins 5 by 5 3) Put the bins-of-bins in bins-of-bins-of-bins 5 by 5; 4) ... 5) Repeat until you have only one bin left. — Stef, Sep 18 '20 at 12:45
The order of the array is important, it should be maintained in the tree somehow. The tree "bins" or "blocks" are specified in advance, that they should contain 5-items max. Does that help? Then as the array grows, the nesting in the tree gets deeper and deeper. But each layer can only have 5 items per block. — Lance, Sep 18 '20 at 12:45
No there are arbitrary number of items in the array. The "bin size" or "block size" is arbitrary as well (or should be a parameter). But in this example I made it 5. — Lance, Sep 18 '20 at 12:47
So if there are a thousand numbers in the input array, more levels should be created? Meaning the rule is that any array at any level must have either 4 or 5 children? — ibrahim mahrir, Sep 18 '20 at 12:48
@ibrahimmahrir correct, but each bin can only have 5 items max (or n items in the general case where `bin_max_size` is a parameter). — Lance, Sep 18 '20 at 12:49
OK, one more question: should arrays at the same level all have the same number of children? Can for example two arrays in level 2 have different number of children (one hase 4 sub-arrays and the other have 5 sub-arrays)? Also can the first level have 5 children instead of 4 so that it's uniform? — ibrahim mahrir, Sep 18 '20 at 12:50
@ibrahimmahrir I added another example. I don't have a good answer to your last question, I am not sure. As long as the bin size is no larger than the max for each level, and the order of the array is maintained, then it doesn't matter I guess. Actually I guess, keep the depth as shallow as possible (but meanwhile keeping under or equal to max bin size). — Lance, Sep 18 '20 at 12:52
**Decision trees** libraries include algorithms to decide how to distribute datapoints on the leaves of a tree; these algorithms usually accept optional parameters such as max number of child per node, and max number of datapoints per leaf. Although you are only interested in a simple tree as opposed to a decision tree, you could use such a library function to build a decision tree solving a trivial decision problem. — Stef, Sep 18 '20 at 13:59

Nenad Vracar · Accepted Answer · 2020-09-18T13:02:00.310

You could use recursive approach where you start from the inner most chunk size and then divide that output on each level up. So as long as the result length is larger then the size param you divide it by calling the function.

const data = [
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0
]

function divide(data, size) {
  const result = []

  for (let i = 0; i < data.length; i += size) {
    const chunk = data.slice(i, i + size);
    result.push(chunk)
  }

  if (result.length > size) {
    return divide(result, size)
  }

  return result;
}

const result = divide(data, 5);
console.log(result)

Such a simple algorithm, yet I am struggling to visualize it in my head haha. The "building the tree from the bottom up" is what's getting me. Thank you for this! — Lance, Sep 18 '20 at 12:55

How to convert an array of integers to a tree?

1 Answers1

Linked