Representing a tree with ordered child nodes

Question

I have some tree-structured data represented as a parent-child relation array:

const tree = [{id:0, parent:-1}, 
              {id:1, parent:0}, 
              {id:2, parent:0}, 
              {id:3, parent:1}, 
              {id:4, parent:2}, 
              {id:5, parent:2}, 
              {id:6, parent:2}]

This results in the following tree:

-0
 |-1
   |-3
 |-2
   |-4
   |-5
   |-6

I would like to make the tree "sortable" so that the order of a node's children can be manipulated, e.g. node 2's children can be reordered to 5,4,6 as follows:

-0
 |-1
   |-3
 |-2
   |-5
   |-4
   |-6

What sort of data structure would best facilitate this?

The only two possibilities I can think of are a nested structure:

const nested = [
  {
    id:0,
    children: [
      {
        id: 1, 
        children: [{id: 3, children:[]}]
      }, 
      {
        id:2, 
        children: [
          {
            id:4, children:[]
          }, 
          {
            id:5, children:[]
          }, 
          {
            id:6, children:[]
          }
        ]
      }
    ]
  }
]

This would require the use of recursive functions, which doesn't seem as performant as the flat structure of the parent-child relation array above.

Alternatively, I could explicitly store the child order as an array in the parent's entry in the parent-child relation array:

const tree2 = [{id:0, parent:-1, children=[1,2]}, 
  {id:1, parent:0, children=[3]}, 
  {id:2, parent:0, children=[4,5,6]}, 
  {id:3, parent:1, children=[]}, 
  {id:4, parent:2, children=[]}, 
  {id:5, parent:2, children=[]}, 
  {id:6, parent:2, children=[]}]

But I'm not sure how correct this is since the children array is redundant information.

Answer 1

You can keep the structure as you have it, since the array implies a sort order. While the relative order is irrelevant for pairs of entries that are not siblings, it does give that order-information to siblings.

What really is the most suitable data structure depends on all other actions you need to perform on it (find, insert, delete, update, get min, iterate,...). The more types of actions, the more you'll find advantages in using a proper nested tree data structure, with maybe some self-balancing features like search trees tend to have (AVL, red-black, B-tree, ...)

Answer 2

You could add a sequence property to each 'node' in your list:

const tree = [
  { id:0 , seq: 0, parent: -1 }, 
  { id:1 , seq: 0, parent:  0 }, 
  { id:2 , seq: 1, parent:  0 }, 
  { id:3 , seq: 0, parent:  1 }, 
  { id:4 , seq: 0, parent:  2 }, 
  { id:5 , seq: 1, parent:  2 }, 
  { id:6 , seq: 2, parent:  2 },
];

But that's clunky. Just represent the data as the tree that it is. A recursive tree walk is pretty trivial to do. And any recursive function can be converted to iteration simply by using an explicit stack or queue, viz:

const tree = {
    id: 0,
    children: [
        {
            id: 1,
            children: [
                { id: 3, children: [], },
            ],
        },
        {
            id: 2,
            children: [
                { id: 4, children: [], },
                { id: 5, children: [], },
                { id: 6, children: [], },
            ],
        },
    ],
};

function *visit_recursive(tree) {

    yield *walk([], tree);
    return;

    function *walk( parents, root ) {
        // if there is no node, we're done.
        if (!root) {
            return;
        }

        // first, yield the current (root) node
        yield { path: parents, node: root };

        parents.push(root.id);
        for (const child of root.children) {
            yield *walk( parents, child );
        }
        parents.pop();

        return;
    }

}

function *visit_iterative(tree) {
    const pending = [ {path: [], node: tree } ];

    while ( pending.length > 0 ) {
        const { path, node } = pending.shift();

        yield { path, node };

        for ( const child of node.children ) {
            pending.push( {path: [...path, node.id], node:child} );
        }

    }

}

console.log('Recursive Traversal:');
for (const item of visit_recursive(tree) ) {
    const { path, node } = item;
    console.log(`${['{root}', ...path, node.id].join(' > ')}: child_count=${node.children.length}` );
}

console.log();

console.log('Iterative Traversal:');
for (const item of visit_iterative(tree) ) {
    const { path, node } = item;
    console.log(`${['{root}', ...path, node.id].join(' > ')}: child_count=${node.children.length}` );
}

Running this will give you output like this (formatted for tidiness):

Recursive Traversal:

{root} > 0         : child_count=2
{root} > 0 > 1     : child_count=1
{root} > 0 > 1 > 3 : child_count=0
{root} > 0 > 2     : child_count=3
{root} > 0 > 2 > 4 : child_count=0
{root} > 0 > 2 > 5 : child_count=0
{root} > 0 > 2 > 6 : child_count=0

Iterative Traversal:

{root} > 0         : child_count=2
{root} > 0 > 1     : child_count=1
{root} > 0 > 2     : child_count=3
{root} > 0 > 1 > 3 : child_count=0
{root} > 0 > 2 > 4 : child_count=0
{root} > 0 > 2 > 5 : child_count=0
{root} > 0 > 2 > 6 : child_count=0