Create a Tree array from a flat array in Angular

For concreteness, I will define your array like this

const arr: Data[] = [
  { name: 'teste', previousName: 'fathername', showOrder: '1', preferredOrder: '2' },
  { name: 'teste 2', previousName: 'fathername', showOrder: '1', preferredOrder: '2' },
  { name: 'teste 3', previousName: 'teste', showOrder: '1', preferredOrder: '2' },
  { name: 'teste 4', previousName: 'teste', showOrder: '1', preferredOrder: '2' },
  { name: 'teste 5', previousName: 'teste 3', showOrder: '1', preferredOrder: '2' },
  { name: 'teste 6', previousName: 'teste 5', showOrder: '1', preferredOrder: '2' },
]

where Data is the following interface:

interface Data {
  name: string,
  previousName: string,
  showOrder: string;
  preferredOrder: string
}

And the goal is to implement the makeTreeNode() function with the following call signature:

declare function makeTreeNode(array: Data[]): Tree<Data>[];

where Tree is a generic class like

class Tree<T> {
  constructor(
    public label: string,
    public data: T,
    public children: Tree<T>[] = [],
    public draggable = true,
    public droppable = true
  ) { }
}

Here's one possible approach:

function makeTreeNode(array: Data[]) {

  // keep a mapping from node name to node:
  const nodeMap: Record<string, Tree<Data>> = {};
  array.forEach(element => 
    nodeMap[element.name] = new Tree(element.name, element)
  );
  
  // populate the children
  array.forEach(element =>
    nodeMap[element.previousName]?.children.push(nodeMap[element.name])
  );

  // return only the nodes without a parent
  return Object.values(nodeMap).filter(n => 
    !(n.data.previousName in nodeMap)
  );
  
}

There are three steps:

• For each Data element, create a corresponding Tree<Data> node (with an empty children array) and put it in nodeMap at the key corresponding to the element name. This lets us easily look up nodes by name later.

• For each Data element, find the corresponding node in nodeMap, and push it onto the children array of the node corresponding to the name of its parent. When this is done, all the nodes' children arrays will be fully populated.

• Filter the array of Tree<Data> elements in the values of nodeMap so that we only keep those elements that have no parent element in nodeMap. This is an array of the root elements, and it is this array that we return.

Let's test it out:

function displayTreeNodes(array: Tree<Data>[]): string {
  return "[" + array.map(t => t.label + ": " + displayTreeNodes(t.children)).join(", ") + "]"
}
console.log(displayTreeNodes(rootNodes));
// "[teste: [teste 3: [teste 5: [teste 6: []]], teste 4: []], teste 2: []]" 

Looks good, we now have a tree structure with two root nodes.

Note that the implementation of makeTreeNode() could be improved to avoid an extra loop through the array, by collapsing the last two steps into one:

// populate children and return array
const ret: Tree<Data>[] = [];
array.forEach(element =>
  (nodeMap[element.previousName]?.children ?? ret).push(nodeMap[element.name])
)
return ret;

But I presented the original version since it demonstrates the concepts more clearly.

Playground link to code