Lowest time complexity to construct tree (nonbinary, unbalanced) from a list?

Question

Suppose I have a list/array like:

[
    { id: 1, parent: null },
    { id: 2, parent: 1 },
    { id: 4, parent: 2 },
    { id: 5, parent: 3 },
    { id: 6, parent: 2 },
    { id: 3, parent: 4 }
]

And I want to convert it to a tree like so:

{ 
    id: null,
    children: [
        { 
            id: 1,
            children: [
                { 
                    id: 2,
                    children: [
                        { 
                            id: 4,
                            children: [
                                {
                                    id: 3,
                                    children: [
                                        {
                                            id: 5,
                                            children: []
                                        }
                                    ]
                                }
                            ]
                        },
                        {
                            id: 6,
                            children: [
                                
                            ]
                        }
                    ]
                }
            ]
        }
    ]
}

I can do this trivially with the following (pseudocode) function:

function GetChildren(rootNode, inputList) {
    for (item in inputList) {
        if (item.parent == rootNode.id) {
            childNode = {
                id: item.id,
                children: []
            }
            GetChildren(childNode, inputList)
            rootNode.children.append(childNode)
        }
    }
}

I believe this will run with time complexity of O(n²). Is there an algorithm that can do this faster? I have seen some similar sounding questions for BSTs, but this is not a BST.

Note the following:

A node may have unlimited children
The tree can be infinitely deep
The items in the list may appear in any order (child may appear before parent)

I had a thought about trying to only pass the part of the list without the parent, so as you recur you iterate through a progressively smaller list. I don't know if that would actually save time though:

function GetChildren(rootNode, inputList) {
    for (item in inputList) {
        listWithoutParent = inputList.remove(rootNode) // O(?)
        if (item.parent == rootNode.id) {
            childNode = {
                id: item.id,
                children: []
            }
            GetChildren(childNode, listWithoutParent)
            rootNode.children.append(childNode)
        }
    }
}

You acn achieve this faster by using a map/lookup table. Check out this question: https://stackoverflow.com/questions/444296/how-to-efficiently-build-a-tree-from-a-flat-structure — Berthur, Apr 29 '21 at 23:38

score 2 · Accepted Answer · answered Apr 30 '21 at 06:48

The idea is to maintain a hash table, keyed by id, where the values are the objects of the tree to be created. So for instance, in that hash table you would have an entry like this:

key: 1
value: { id: 1, children: [] }

While you iterate the input data, look up the value for the current id, and for the current parent. If either does not yet figure in the hash table, insert it at that moment. This gives you two objects with id and children properties. Then append the child node object to the children array of the parent object.

Here is how that could work in JavaScript, where for a hash table I use the native Map:

function getOrCreateNode(map, id) {
    let node = map.get(id);
    if (node == undefined) { // Node not yet created
        node = { id, children: [] }; // Create a new node
        map.set(id, node); // Add that new node to the map by its id
    }
    return node;
}

function createTree(data) {
    let map = new Map; // Keys are id, values are nodes of the tree 
    for (let item of data) { // Iterate all objects in the input array
        // Get parent and child object, and add child object to parent's children array:
        getOrCreateNode(map, item.parent).children.push(getOrCreateNode(map, item.id));
    }
    return map.get(null); // Return the root node
}

// Sample input data:
let data = [
    { id: 1, parent: null },
    { id: 2, parent: 1 },
    { id: 4, parent: 2 },
    { id: 5, parent: 3 },
    { id: 6, parent: 2 },
    { id: 3, parent: 4 }
];

// Output the result
console.log(createTree(data));

As hash tables typically provide insert and look up implementations that have an average amortised constant time complexity, this algorithm will run with a linear time complexity (in terms of the number of entries in the input array).

We should add the disclaimer that insert and lookup operations on a hash table have a theoretical worst time complexity that is linear to its size. Sometimes you may know more about the id values, such that you can use a perfect hashing algorithm. For instance, the id values could all be small unsigned integers (like in your example). In that case you can use an array as hash table, and the id values as array indexes. Then the worst case time complexity for an insert or lookup operation is still O(1).

Lowest time complexity to construct tree (nonbinary, unbalanced) from a list?

1 Answers1