How To Return The Tree Node By Index When Tree Nodes Have Subtree Size?

Say I have this piece of demo data: { size: 100, type: 'container', list: [ { size: 30, type: 'container', list: [ { size: 10,

Solution 1:

No, it's incorrect, index <= endSize should be index < endSize. In the worst case this would lead to an infinite loop on an empty node.

Also a recursive solution would have been much simpler than the iterative version:

const getLeafContaining = (tree, index) => {
  if (index < tree.size) {
    if (node.type == 'leaf') {
      return { node, index };
    } elseif (node.type == 'container') {
      let before = 0for (const node of nodes) {
        const after = before + node.size;
        if (index < after) {
          return getLeafContaining(node, index - before);
        }
        before = after;
      }
    }
  }
  return { node: null, index: -1 }
}

An alternative to the accumulating before sum would be to decrement index:

for (const node of nodes) {
        if (index < node.size) {
          return getLeafContaining(node, index);
        }
        index -= node.size;
      }