How to neatly association next and previous "node" within a tree structure?

Question

Say I have a simple tree structure:

{
  label: 'a',
  children: [
    {
      label: 'a.a',
      children: [
        {
          label: 'a.a.a',
          children: [
            {
              label: 'a.a.a.a'
            },
            {
              label: 'a.a.a.b'
            },
            {
              label: 'a.a.a.c'
            },
            {
              label: 'a.a.a.d'
            }
          ]
        },
        {
          label: 'a.a.b',
          children: [
            {
              label: 'a.a.b.a'
            },
            {
              label: 'a.a.b.b'
            }
          ]
        },
        {
          label: 'a.a.c',
          children: [
            {
              label: 'a.a.c.a'
            }
          ]
        },
        {
          label: 'a.a.d',
          children: [
            {
              label: 'a.a.d.a'
            },
            {
              label: 'a.a.d.b'
            }
          ]
        }
      ]
    },
    {
      label: 'a.b',
      children: [
        {
          label: 'a.b.a',
          children: [
            {
              label: 'a.b.a.a'
            },
            {
              label: 'a.b.a.b'
            },
            {
              label: 'a.b.a.c'
            },
            {
              label: 'a.b.a.d'
            }
          ]
        },
        {
          label: 'a.b.b',
          children: [
            {
              label: 'a.b.b.a'
            },
            {
              label: 'a.b.b.b'
            }
          ]
        }
      ]
    }
  ]
}

How do I neatly figure out a.b.a.a comes after a.a.d.b (next), and a.b.a.d comes before a.b.b.a (previous), for example?

That is, you go from leaf to leaf, even if the leaves aren't directly siblings. If they are siblings, you just go to the next/previous sibling, but if they are not siblings, you must navigate up and down the tree to find the next and previous ones.

What is a simple way to accomplish this? I have been at this for a bit and am stuck doing it in a non-hacky way. Basically I try doing itsy-bitsy incremental manual checks, like checking if the parent is a leaf, and if not, checking down, and then I get lost.

You can add a .parent property to keep track of the parent if that helps, or you can pass down the path (assume the label isn't actually the path as shown, that is just for illustrative purposes).

function linkNext(node) {
  const i = node.parent.indexOf(node)
  if (i < node.parent.children.length - 1) {
    node.next = node.parent.children[i + 1]
  } else {
    if (node.parent.parent) {
      // I get lost about here.
    }
  }
}

function linkPrevious(node) {
  const i = node.parent.indexOf(node)
  if (i > 0) {
    node.next = node.parent.children[i - 1]
  } else {
    // same here...
  }
}

Wondering how this can be done in a straightforward way, my mind gets tripped up on this problem.

Answer 1

For this purpose you may benefit from a generator function: it could yield the leaves in their order:

function* leaves(node) {
    if (!node.children) { // It's a leaf
        return yield node;
    }
    for (const child of node.children) {
        yield* leaves(child);
    }
}

Once you have that, you can visit the leaves with a simple for..of loop:

for (const leaf of leaves(tree)) {
    console.log(leaf.label); 
}

To have the same in the reverse order, you could extend the generator with an optional argument:

function* leaves(node, reversed=false) {
    if (!node.children) { // It's a leaf
        return yield node;
    }
    const children = reversed ? node.children.toReversed() : node.children;
    for (const child of children) {
        yield* leaves(child, reversed);
    }
}

Maybe this is already enough for your purpose, but if you really want to add next properties to leaf nodes, then you could benefit from a function that would yield leaves together with their successors (as an array of two nodes). Here is a generic function to get that:

function* pairs(iterable) {
    const iterator = iterable[Symbol.iterator]();
    let prev = iterator.next().value;
    for (const next of iterator) {
        yield [prev, next];
        prev = next;
    }
}

And then the linking of leaves is as simple as:

for (const [prev, next] of pairs(leaves(tree, reversed))) {
    prev.next = next;
}

Here is all that put together, using your sample tree as input:

function* leaves(node, reversed=false) {
    if (!node.children) { // It's a leaf
        return yield node;
    }
    const children = reversed ? node.children.toReversed() : node.children;
    for (const child of children) {
        yield* leaves(child, reversed);
    }
}

// Generic function to iterate the consecutive pairs of an iterable
function* pairs(iterable) {
    const iterator = iterable[Symbol.iterator]();
    let prev = iterator.next().value;
    for (const next of iterator) {
        yield [prev, next];
        prev = next;
    }
}

function linkNext(node, reversed=false) {
    for (const [prev, next] of pairs(leaves(tree, reversed))) {
        prev.next = next;
    }
}

// Example run
const tree = {label: 'a',children: [{label: 'a.a',children: [{label: 'a.a.a',children: [{label: 'a.a.a.a'},{label: 'a.a.a.b'},{label: 'a.a.a.c'},{label: 'a.a.a.d'}]},{
label: 'a.a.b',children: [{label: 'a.a.b.a'},{label: 'a.a.b.b'}]},{label: 'a.a.c',children: [{label: 'a.a.c.a'}]},{label: 'a.a.d',children: [{label: 'a.a.d.a'},{label: 'a.a.d.b'}]}]},{label: 'a.b',children: [{label: 'a.b.a',children: [{label: 'a.b.a.a'},{label: 'a.b.a.b'},{label: 'a.b.a.c'},{label: 'a.b.a.d'}]},{label: 'a.b.b',children: [{label: 'a.b.b.a'},{label: 'a.b.b.b'}]}]}]}

console.log("Iterate the leaves in their order:");
for (const node of leaves(tree)) console.log(node.label);
console.log("Iterate the leaves in reversed order");
for (const node of leaves(tree, true)) console.log(node.label);
// Set the next properties of leaves (only leaves!)
linkNext(tree);