Convert list to tree by descendants and ancestors

Question

I am trying to convert the list to a tree using descendants and ancestors params in the element:

I have for example something like this:

const itemToUpdate = {
  id: 1,
  ancestors: [
    {
      id: 2,
      ancestors: [
        {
          id: 4
        }
      ]
    }
  ],
  descendants: [
    {
      id: 3,
      descendants: [
        {
          id: 5
        },
        {
          id: 6,
          descendants: [
            {
              id: 8
            },
            {
              id: 9
            }
          ]
        },
        {
          id: 7
        }
      ]
    }
  ]
};

const updatedItem = {
  id: 4,
  children: [
    {
      id: 2,
      children: [
        {
          id: 1,
          children: [
            {
              id: 3,
              children: [
                {
                  id: 5
                },
                {
                  id: 6,
                  children: [
                    {
                      id: 8
                    },
                    {
                      id: 9
                    }
                  ]
                },
                {
                  id: 7
                }
              ]
            }
          ]
        }
      ]
    }
  ]
};

The point is that trees can be nested up to many levels. Additionally, there can be many ancestors and descendants on the level, so I need a more generic solution. The tree must be created upward from ancestors and downward from descendants.

I found a way to get descendants of the tree, but I still need to add to that ancestors on the top of this tree:

export const convertListToTree = <T extends ApiTree<T>>(list: Array<T>, key = 'ascendants'): Array<T> => {
  const getNestedItem = (path: Array<string>, tree: Array<T>): T => {
    const nestedItem = tree.find(nestedItem => nestedItem.id === path[0]);
    const newPath = path.slice(1);
    if (!newPath.length) {
      return nestedItem;
    } else if (nestedItem?.[key]) {
      return getNestedItem(newPath, nestedItem?.[key]);
    } else {
      return getNestedItem(newPath, tree);
    }
  };

  const sortListByPathLength = (list: Array<T>): Array<T> => {
    return sortBy(list, (item: T) => item.path?.length);
  };

  const addRootItem = (item: T, tree: Array<T>): void => {
    tree.push(item);
  };

  const addChildrenItem = (item: T, tree: Array<T>): void => {
    const parent = getNestedItem(item.path, tree);
    if (parent) {
      parent[key].push(item);
    } else {
      addRootItem(item, tree);
    }
  };

  const tree = [];
  if (list?.length) {
    const sortedList = sortListByPathLength(list);
    sortedList.forEach(item => {
      if (!item.path?.length) {
        addRootItem(item, tree);
      } else {
        addChildrenItem(item, tree);
      }
    });
  }
  return tree;
};

Any advice will be more than welcome. 🙏

Answer 1

Assuming that there is only one ancestor for each level, you could take a recursive function that keeps the children but returns the earliest ancestor node.

const
    fn = ({ id, ancestors, descendants }, children) => {
        const node = { id };
        if (Array.isArray(children)) node.children = children;
        if (descendants) node.children = descendants.map(fn);
        return ancestors
            ? fn(ancestors[0], [node])
            : node;
    },
    data = { id: 1, ancestors: [{ id: 2, ancestors: [{ id: 4 }] }], descendants: [{ id: 3, descendants: [{ id: 5 }] }] },
    result = fn(data);

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }