About the tree, and about Typescript

Most of the time in my college days, I had been learning about the binary tree, where each node has no more than two children. In my work, I more often see a tree with several children in a single node, though.

In this article, I am going to use Typescript. These days, I mostly work with the .NET (using C#) and Angular frameworks (using Typescript), but I have solved a similar problem in Angular, so, yes, let’s do it again and try to improve it this time.

Define a type

Pretend that I had created a .ts file called tree.ts . First of all, let’s define an interface called INode that takes a type argument indicating its id type. Every node in the tree should have its own id and a child list.

export interface INode<T extends string | number> {
	id: T;
  children: INode<T>[];
}

Iterate nodes

The first thing that comes to mind is probably traversing through nodes. Fortunately, Typescript (actually Javascript) has the array’s foreach built-in function, so we just leverage that.

export function foreachNode<T extends string | number>(
  nodes: INode<T>[] | INode<T>,
  callbackFn: (node: INode<T>) => void
): void {
  const foreachFn = (node: INode<T>) => {
    callbackFn(node);
    node.children.forEach(callbackFn);
  };
  Array.isArray(nodes) ? nodes.forEach(foreachNode) : foreachFn(nodes);
}

My plan is to invoke the callback argument on a specific node, then recursively execute the same callback on each element of its child list. After all, it looks like the code above.

Find a node (DFS)

So far, we have our way of traversing the tree in depth. I am going to use the same approach to do a linear search on each child list.

If the tree's depth is greater than its width, this method will outperform BFS in terms of performance. The implementation should be like this

export function findNode<T extends string | number>(
  nodes: INode<T>[] | INode<T>,
  predicate: (node: INode<T>) => boolean
): INode<T> | undefined {
	const findFn = (node: INode<T>) =>
    predicate(node) ? node : find(node.children, predicate);
       
  return !Array.isArray(nodes) ? findFn(nodes) : nodes.find(node => findFn(node));
}

Convert a flat list to tree

Define the flat list

export interface IFlatModel<T extends string | number> {
  id: T;
  parentId?: T;
}

export interface INode<T extends string | number> {
	id: T;
  children: INode<T>[];
}

export type IList<T extends string | number> = IFlatModel<T>[];

Flat list to tree

export function toTree<T extends string | number>(flatList: IList<T>): Array<INode<T>> {
  return convert(flatList);
}

export function foreach<T extends string | number>(
  nodes: INode<T>[] | INode<T>,
  callbackFn: (node: INode<T>) => void
): void {
  const foreachNode = (node: INode<T>) => {
    callbackFn(node);
    node.children.forEach(callbackFn);
  };
  Array.isArray(nodes) ? nodes.forEach(foreachNode) : foreachNode(nodes);
}

export function find<T extends string | number>(
  nodes: INode<T>[] | INode<T>,
  predicate: (node: INode<T>) => boolean
): INode<T> | undefined {
  const findFn = (node: INode<T>) =>
    predicate(node) ? node : find(node.children, predicate);
  
  return !Array.isArray(nodes) ? findFn(nodes) : nodes.find(node => findFn(node));
}

function convert<T extends string | number>(
  list: IList<T> | INode<T>[]
): INode<T>[] {
  const map = new Map<T, INode<T>>();

  // create nodes without children
  for (const item of list) {
    const node = { ...item, children: [] };
    map.set(node.id, node);
  }

  // link nodes with their parents
  for (const node of map.values()) {
    if (node.parentId !== undefined) {
      const parent = map.get(node.parentId);
      if (parent !== undefined) {
        parent.children.push(node);
      } else {
        console.warn(`Cannot find parent node for ${node.id}`);
      }
    }
  }

  // find root nodes
  const roots: INode<T>[] = [];
  for (const node of map.values()) {
    if (node.parentId === undefined) {
      roots.push(node);
    }
  }

  return roots;
}

Demo