Algorithm to map the input tree so it receives depth and position information, as well as the flat version of its nodes

positionedTree.ts

interface ITreeNode<Data=unknown> {
    id: string|null;
    data: Data;
    children: ITreeNode<Data>[];
}

interface IPositionedTreeNode<Data=unknown> extends ITreeNode<Data> {
    depth: number;
    parentId: ITreeNode<Data>['id'];
}

interface IPositionedTreeOutput<Data=unknown> {
    tree: IPositionedTreeNode<Data>;
    nodes: Record<
        string,
        IPositionedTreeNode<Data>
    >;
}

interface ISplitReducerValue<Data=unknown> {
    childTrees: IPositionedTreeOutput<Data>['tree'][];
    nodes: IPositionedTreeOutput<Data>['nodes'];
}

const tree: ITreeNode<string> = {
    id: '1',
    data: 'A',
    children: [
        {
            id: '2',
            data: 'A->B',
            children: []
        },
        {
            id: '3',
            data: 'A->C',
            children: [
                {
                    id: '4',
                    data: 'C->D',
                    children: []
                }
            ]
        },
        {
            id: '5',
            data: 'A->E',
            children: [
                {
                    id: '6',
                    data: 'E->F',
                    children: [
                        {
                            id: '8',
                            data: 'F->H',
                            children: [
                                {
                                    id: '9',
                                    data: 'H->I',
                                    children: []
                                }
                            ]
                        }
                    ]
                },
                {
                    id: '7',
                    data: 'E->G',
                    children: []
                }
            ]
        }
    ]
};

function ArrayFunctor<Input=unknown, Output=unknown>(
    mapFn: (input: Input) => Output,
    input: Array<Input>
): Array<Output> {
    return input.map(mapFn);
}

function positionedTreeInsert<Data=unknown>(
    parentNodeId: ITreeNode<Data>['id'],
    currentNode: ITreeNode<Data>,
    depthAcc: number,
    nodesAcc: IPositionedTreeOutput<Data>['nodes']
): IPositionedTreeOutput<Data> {
    const positionedCurrentNode: IPositionedTreeNode<Data> = {
        ...currentNode,
        depth: depthAcc,
        parentId: parentNodeId
    };

    switch (true) {
        case currentNode.children.length > 0:            
            const initialReducerValue: ISplitReducerValue<Data> = {
                childTrees: [],
                nodes: {}
            };

            const childInsertSplitOutput = ArrayFunctor(
                childNode => positionedTreeInsert(currentNode.id, childNode, depthAcc + 1, nodesAcc),
                currentNode.children
            ).reduce((acc, current) => ({
                childTrees: [...acc.childTrees, current.tree],
                nodes: {...acc.nodes, ...current.nodes}
            }), initialReducerValue);

            return {
                tree: {
                    ...positionedCurrentNode,
                    children: childInsertSplitOutput.childTrees
                },
                nodes: {
                    ...nodesAcc,
                    ...(positionedCurrentNode.id !== null
                        ? {
                            [positionedCurrentNode.id]: positionedCurrentNode
                        }
                        : {}
                    ),
                    ...childInsertSplitOutput.nodes
                }
            };
        default:
            return {
                tree: positionedCurrentNode,
                nodes: {
                    ...nodesAcc,
                    ...(positionedCurrentNode.id !== null
                        ? {
                            [positionedCurrentNode.id]: positionedCurrentNode
                        }
                        : {}
                    )
                }
            };
    }
}

const positionedTreeOutput = positionedTreeInsert(null, tree, 0, {});
console.log(positionedTreeOutput);