How To Incrementally Build An Array Tree Where Each Array Can Only Have 1, 2, 4, 8, 16, Or 32 Items?

At a high level, what I am trying to do is build up a 'tree array' structure, exactly like in the tree array structure in this answer, with one additional constraint: every array c

Solution 1:

I went for the null option for internal levels as well, like you suggested:

I guess it could also be null (-), either one would work, whatever is easier, so it could be this too.

You also wrote:

every item, which can be anything, even arrays!

For your previous question I used an Array-check to detect whether an item in the tree was a leaf or not, but as that would not work here, I added a property in my Tree class that keeps track of the height of the tree.

As arrays will be padded with null values, JavaScript's length property will not give a clue about where to insert the next item. To avoid that the code would repeatedly have to iterate such arrays to find the index of the first null, I decided to keep track of the data sizes (so not counting the null padding) of the arrays that are on the path to the last inserted item. This way I have both the height of the tree (as length of this path), and the information where the next null is that can be used for storing the new item.

This path-based solution has also the advantage that you can actually store null items if you really wanted to. Although impossible to distinguish from the padding, you would notice the difference once you add another non-null value after that. The previously added null item will remain in tact.

Here is the implementation:

classTree {
    constructor(maxPower=5) {
        this.root = null;
        this.maxSize = 2**maxPower; // default: 32// Path of rightmost data-branch from bottom to top://   It will have {node, size} objectsthis.rightPath = []; 
    }
    add(value) {
        for (let level ofthis.rightPath) {
            let {node, size} = level;
            if (size < this.maxSize) {
                // Double array size when there is no more room:if (size === node.length) node.push(...Array(size).fill(null));
                node[size] = value; // This is the empty spot to use
                level.size++; // Update size on the pathreturn;
            }
            // If we get here, there was no available spot at this level// Wrap the value so when it gets inserted at a higher level,//    the core value will still end up at the bottom level.
            value = [value];
            // Update path accordingly (for use in future `add` calls)
            level.node = value;
            level.size = 1;
        }
        // If we get here, there was no available spot in the tree: //    add a level at the topthis.root = this.root ? [this.root, value] : [value];
        // Update path accordinglythis.rightPath.push({ node: this.root, size: this.root.length });
    }
}

// Demolet tree = newTree;
for (let i = 1; i <= 65; i++) {
    tree.add(i);
    console.log(JSON.stringify(tree.root));
}