Converts flat list into tree

flatIntoTree.ts

type FlatItem<U> = {
  uuid: U;
  parent: U | null;
};

export type TreeBranch<T> = Omit<T, 'parent'> & {
  parent: TreeBranch<T> | null;
  children: TreeBranch<T>[];
};

export type Tree<T extends FlatItem<T['uuid']>> = {
  branches: TreeBranch<T>[];
  nodes: Map<T['uuid'], TreeBranch<T>>;
};

const tmpBranch = <T>(item: T): TreeBranch<T> => ({
  ...item,
  parent: null, // just null parent for now
  children: [], // will push children later
});

/**
 * Converts flat list into tree.
 */
export const flatIntoTree = <T extends FlatItem<T['uuid']>>(
  flat: T[],
): Tree<T> => {
  const branches: TreeBranch<T>[] = [];

  // 1) create map of tmp nodes
  const nodes = new Map<T['uuid'], TreeBranch<T>>(
    flat.map(item => [item.uuid, tmpBranch(item)]),
  );

  // 2) setup parent & push children
  for (const { uuid, parent } of flat) {
    const self = nodes.get(uuid)!;
    if (parent !== null) {
      self.parent = nodes.get(parent) ?? null;
      if (self.parent !== null) {
        self.parent.children.push(self);
      }
    } else {
      branches.push(self);
    }
  }

  return { branches, nodes };
};