Tree <--> List conversion

tree_list_conversion.js

function createTree(list) {

    var map = {}, node, roots = [], i;

    for (i = 0; i < list.length; i += 1) {
        map[list[i].id] = i; // initialize the map
        list[i].children = []; // initialize the children
    }

    for (i = 0; i < list.length; i += 1) {
        node = list[i];

        if (node.parent_id === null) {
            roots.push(node);
        } else {
            // if you have dangling branches check that map[node.parent_id] exists
            // if (map[node.parent_id]) {
            list[map[node.parent_id]].children.push(node);
            // }
        }
    }

    return roots;
}

function flatTree(tree) {

    if (tree.length === 0) return [];

    let i = 0;
    let stack: { tree: [], i: number }[] = [];
    let ret = [];

    while (true) {

        if (i === tree.length) {

            if (stack.length === 0) {
                // no more items on the stack
                return ret;
            }

            // restore the current state
            let tuple = stack.shift();
            i = tuple.i;
            tree = tuple.tree;
            continue;
        }

        let current = tree[i];

        ret.push({
            id: current.id,
            parent_id: current.parent_id
        })

        if (current.children && current.children.length) {
            // back up current state
            stack.unshift({ tree: tree, i: i + 1 });
            tree = current.children;
            i = 0;
            continue;
        }

        i++;

    }

}


function main() {
    var list = [
        { id: 1, parent_id: null },
        { id: 2, parent_id: 1 },
        { id: 3, parent_id: 2 },
        { id: 4, parent_id: 2 },
        { id: 5, parent_id: null },
    ];

    var tree = [
        {
            id: 1, parent_id: null,
            children: [
                {
                    id: 2, parent_id: 1,
                    children: [
                        { id: 3, parent_id: 2, children: [] },
                        { id: 4, parent_id: 2, children: [] },
                    ]
                },
            ]
        },
        { id: 5, parent_id: null, children: [] },
    ];
}