LuuVinhLoc
Vietnamese / Japanese / Eng blog

Vietnamese / Japanese / Eng blog

Converts flat list to tree 🌲 with Typescript and no any type

Converts flat list to tree 🌲 with Typescript and no any type

LuuVinhLoc's photo
LuuVinhLoc
·Mar 31, 2021·

2 min read

Flat list is an array of items that has no children with ids and parent ids.

Purpose

Example

Input

export interface IFolder {
  folderId: number;
  folderParentId: number;
  name: string;
}

const folderArr = [
  { folderId: 1, folderParentId: 0, name: 'root' },
  { folderId: 2, folderParentId: 1, name: 'A' },
  { folderId: 3, folderParentId: 1, name: 'B' },
  { folderId: 4, folderParentId: 3, name: 'C' },
];

Output

const folderTree = [
  {
    folderId: 1,
    folderParentId: 0,
    name: "root",
    children: [
      { folderId: 2, folderParentId: 1, name: "A", children: [] },
      {
        folderId: 3,
        folderParentId: 1,
        name: "B",
        children: [{ folderId: 4, folderParentId: 3, name: "C", children: [] }]
      }
    ]
  }
];

Tree model for type checking

/**
 * like `interface` prefix, `type` prefix is `T`
 */
export type TTree<T> = {
  children?: TTree<T>[];
} & T;

Converts

import { TTree } from '@model';

/**
 * flat list to tree
 *
 * @param list - a flat list
 * @param params - `{ id, parentId }`: id name and parentId name
 * @example `arrayToTree<IFolder>(folderArr, { id: 'folderId', parentId: 'folderParentId' });`
 * @returns `TTree`
 */
export const arrayToTree = <T>(
  list: T[],
  { id, parentId }: { id: string; parentId: string }
): TTree<T>[] | [] => {
  /** map between id and array position */
  const map: number[] = [];
  const treeList: TTree<T>[] = list as TTree<T>[];

  for (let i = 0; i < treeList.length; i += 1) {
    /** initialize the map */
    map[(treeList[i] as TTree<T> & { [id: string]: number })[id]] = i;
    /** initialize the children */
    treeList[i].children = [];
  }

  let node: TTree<T> & { [parentId: string]: number };
  /** return value */
  const roots: TTree<T>[] = [];

  for (const item of treeList) {
    node = item as TTree<T> & { [parentId: string]: number };
    if (node[parentId] !== 0) {
      if (treeList[map[node[parentId]]] !== undefined) {
        treeList[map[node[parentId]]].children?.push(node);
      }
    } else {
      roots.push(node);
    }
  }
  return roots;
};

Demo

You can use my demo in stackblitz.


Photo by Fabrice Villard on Unsplash

 
Share this