Immutable N-ary tree?

[ornamentist]

Hi,

I'd like to create an n-ary tree using Rimbu. My first thought was a directed acyclic graph (DAG) using the Rimbu graph support. I would need to ensure the acyclic condition myself. Is that a bad idea?

[vitoke]

I'm not sure whether a Graph is the best fit for an n-ary tree. The thing is that in a rimbu Graph, each node is unique. That means that each value could appear only once in the entire tree. Usually, for a tree, that is not the case. If you really want to use a Graph, you could consider creating unique invisible nodes, and store the tree values in the edge values, but that can become quite complex.

Depending on your use case, I would expect a recursive data structure using a map-like structure, for example:

import { HashMap, type RMap } from "@rimbu/core";

// Recursive tree type
type NTree<T> = RMap<T, NTree<T>>;

// example instances
const emptyTree: NTree<number> = HashMap.empty();
const tree1: NTree<number> = HashMap.of([1, emptyTree], [2, emptyTree]);
const tree2: NTree<number> = HashMap.of([5, emptyTree], [6, tree1], [7, tree1]);

// conversion to JS arrays
type NTreeJS<T> = ReadonlyArray<readonly [T, NTreeJS<T>]>;

function toJS<T>(ntree: NTree<T>): NTreeJS<T> {
  return ntree
    .stream()
    .map(([value, tree]) => [value, toJS(tree)] as const)
    .toArray();
}

console.log(toJS(tree2));

While in theory it's possible to create cycles in this tree structure, you would have to go through quite some effort to create one. Preventing cycles completely, also in a graph, is a hard problem since you probably need to store nodes already added in a separate structure.

Curious to hear how you continue your quest.

[ornamentist]

That's an intriguing suggestion, thanks. I think I could also wrap node values in a singleton List to get around the uniqueness issue. I'll try some experiments and update this thread.