How do you create this tree data structure one item at a time?

Question

Here is the way this data structure / algorithm should work (each line is 1 step):

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

You'll notice that at each level, the numbers are all at the same level in the tree.
And at every level each array can only have 3 items before things change.
You'll notice on the transition from step 4 to 5, it has to nest the arrays one level further down.
The transition from step 10 to 11 also nests again further.
The pattern will continue to nest as each level gets 3 items.
As seen in step 11, when you add the next item, it is added at the proper depth of the tree.
All numbers (arbitrary "items" really) are at the same depth level in the tree.

The tricky part is, when you reach the "end" of a particular run, how do you traverse the arrays and insert the new arrays in the appropriate spots? What is the general algorithm to implement this concisely? Ideally not a functional algorithm but a regular procedural/imperative one. My attempt is here. Essentially this is pushing an item in a "tree array", keeping every item/object/number at the same depth level at the leaves of the tree.

I am struggling when it comes to how to traverse up and down the tree to add a new item when the nesting level changes.

Note: I used numbers to demonstrate the order they were added. But they shouldn't be used in the final algorithm, it should take generic objects.

user_5459839 · Answer

You can use recursion for this.

First recurse into the tree, always choosing the last entry, until you reach the bottom, which can be recognised by the fact that there are no more subarrays there.

Then the backtracking phase will be used to build a new subtree which will eventually be inserted at a free spot. At first this subtree is just the value itself. If there is already room at the bottom level, insert the "subtree" (which is not really a tree) there.

But if there is no room, let the recursive call return a new value: it will be the value wrapped in an array, so like 10 becomes [10]. In the calling function we are one level up. If there is room over there, then insert that value (in the example that would be [10]). If there is no room there either, then wrap the value again and return it to the caller. In the example we would return [[10]].

And so you keep backtracking upwards out of the recursion tree, and making the value "deeper". At some point it can be inserted, and from then onwards the function will just return undefined so to indicate to the caller that the job has already been done, and they should just return undefined also.

In a boundary case, the recursion will backtrack to the original caller without having inserted the value. In that case the return value will be the wrapped value that still needs to go somewhere. So then we make the whole tree deeper, giving it a new root (this is the added level), where the original root becomes the first child, and the wrapped value becomes the second child.

Here is an implementation in JavaScript:

class Tree {
    constructor() {
        this.root = [];
    }
    add(value) {
        const recur = (node) => {
            if (Array.isArray(node[0])) { // Not yet at bottom level
                value = recur(node[node.length-1]); // Recursive call...
                if (value === undefined) return; // done: get out of recursion
            }
            if (node.length === 3) return [value]; // wrap the value to be inserted
            node.push(value); // There is room here: insert the (possibly wrapped) value
            // By returning undefined we indicate the value has been inserted
        };
        
        value = recur(this.root);
        // If tree is full, increase the depth of the tree
        if (value !== undefined) this.root = [this.root, value];
    }
}

// Demo
let tree = new Tree;
for (let i = 1; i < 16; i++) {
    tree.add(i);
    console.log(JSON.stringify(tree.root));
}

Iterative version

The same logic, but without recursion. So now we have a stack (path):

class Tree {
    constructor() {
        this.root = [];
    }
    add(value) {
        let node = this.root;
        let path = []; // ...from root to bottom
        while (Array.isArray(node[0])) { // Not yet at bottom level
            path.push(node); // Keep track where we come from
            node = node[node.length-1]; // Descend in the right arm of the tree
        }
        // We arrived at the bottom. Now let's find a free spot
        while (node && node.length === 3) { // While there is no room...
            value = [value]; // Wrap the value to be inserted as a tree of its own
            node = path.pop(); // Get ancestor node
        }
        // We are now ready to insert the value/subtree
        if (node) { // We found an available spot
            node.push(value);
        } else { // No spot found: tree is full. Add level at the top.
            this.root = [this.root, value];
        }
    }
}
// Demo
let tree = new Tree;
for (let i = 1; i < 16; i++) {
    tree.add(i);
    console.log(JSON.stringify(tree.root));
}

user_1030413 · Answer

Here is a slightly different iterative version.

The difference is that we insert the node in the "correct" spot and then fix the tree. This is slightly less efficient than the accepted solution, but might be interesting from an academic perspective

const add = (tree, node) => {
  const parents = [];
  let cur = tree;
  do {
    parents.push(cur);
    cur = cur[cur.length - 1];
  } while (Array.isArray(cur));

  parents[parents.length - 1].push(node);
  for (let idx = parents.length - 1; idx >= 1; idx -= 1) {
    if (parents[idx].length === 4) {
      parents[idx - 1].push([parents[idx].pop()]);
    }
  }
  if (tree.length === 4) {
    tree.splice(0, 4, tree.slice(0, 3), [tree[3]]);
  }
};

const myTree = [];
for (let id = 1; id <= 16; id += 1) {
  add(myTree, id);
  console.log(JSON.stringify(myTree));
}
// => [1]
// => [1,2]
// => [1,2,3]
// => [[1,2,3],[4]]
// => [[1,2,3],[4,5]]
// => [[1,2,3],[4,5,6]]
// => [[1,2,3],[4,5,6],[7]]
// => [[1,2,3],[4,5,6],[7,8]]
// => [[1,2,3],[4,5,6],[7,8,9]]
// => [[[1,2,3],[4,5,6],[7,8,9]],[[10]]]
// => [[[1,2,3],[4,5,6],[7,8,9]],[[10,11]]]
// => [[[1,2,3],[4,5,6],[7,8,9]],[[10,11,12]]]
// => [[[1,2,3],[4,5,6],[7,8,9]],[[10,11,12],[13]]]
// => [[[1,2,3],[4,5,6],[7,8,9]],[[10,11,12],[13,14]]]
// => [[[1,2,3],[4,5,6],[7,8,9]],[[10,11,12],[13,14,15]]]
// => [[[1,2,3],[4,5,6],[7,8,9]],[[10,11,12],[13,14,15],[16]]]

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

How do you create this tree data structure one item at a time?

2 Answers

Iterative version