Getting the maximum number of nodes in a tree

I would like to get the max number of nodes in a tree. So the max number of nodes is 5 in the example below because there are 5 nodes in the first tree.

Example input is as follows;
[['1 3'], ['1 4'], ['3 5'], ['4 6'], ['7 8']] and the tree becomes like this;

enter image description here

I have written this code and it is working but is it possible to write more efficient code? Because the time complexity is more than O(N²) right now.

function getMaxNumberOfNodes(edges) {
    let nodes = new Map();
    for (let i = 0; i < edges.length; i++) {
        let firstValue = parseInt(edges[i][0].charAt(0));
        let secondValue = parseInt(edges[i][0].charAt(2));

        if (nodes.has(firstValue)) {
            let tempArray = nodes.get(firstValue)
            tempArray.push(secondValue)
            nodes.set(firstValue, tempArray);
        }
        else {
            nodes.set(firstValue, [secondValue]);
        }
    }
    console.log(nodes) // Map(4) { 1 => [ 3, 4 ], 3 => [ 5 ], 4 => [ 6 ], 7 => [ 8 ] }
    let connectedNodes = new Map();
    for (let node of nodes.keys()) {
        let nodeValue = nodes.get(node);
        let tempArray = [];
        for (let i = 0; i < nodeValue.length; i++) {
            if (nodes.has(nodeValue[i])) {
                tempArray = tempArray.concat(nodes.get(nodeValue[i]));
            }
        }
        connectedNodes.set(node, nodes.get(node).concat(tempArray));
    }
    console.log(connectedNodes) // Map(4) { 1 => [ 3, 4, 5, 6 ], 3 => [ 5 ], 4 => [ 6 ], 7 => [ 8 ] }

    let maxNumberOfNodes = 0;

    for (let node of connectedNodes.keys()) {
        maxNumberOfNodes = Math.max(connectedNodes.get(node).length, maxNumberOfNodes);
    }
    return maxNumberOfNodes + 1;
}

console.log(getMaxNumberOfNodes([['1 3'], ['1 4'], ['3 5'], ['4 6'], ['7 8']])) // 5

Leave a Comment