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

10 thoughts on “Getting the maximum number of nodes in a tree”

  1. Find all root nodes in linear time and space (e.g. by building a set of all nodes & child nodes). Then, use DFS to measure the size of each tree in linear time (O(V+E), but E is V-1).

    Reply
  2. I would do it this way:

    let inputTest = [
      ['1 3'],
      ['1 4'],
      ['3 5'],
      ['4 6'],
      ['7 8']
    ];
    
    function groupByRootNode(inp) {
      let root = new Map();
      let nodes = new Map();
    
      inp.forEach(pair => {
        let [prev, next] = pair[0].split(' ');
        //find the group either on the nodes map or the root map
        let group = nodes.get(prev) || root.get(prev);
        //if group exists
        if (group) {
          //add pair to existing group
          group.push(pair);
          if (root.has(next)) {
            //if theres a root node with next, then that is no longer a root node
            root.delete(next);
          }
          //record new node as part of group
          nodes.set(next, group);
        } else {
          //else group doesn't exist
          //we create a new tree group
          //prev is a new root node
          group = [pair]
          nodes.set(next, group);
          root.set(prev, group);
        }
      });
      return root;
    }
    
    console.log(Array.from(groupByRootNode(inputTest),
      ([root, group]) => ({
        rootNode: root,
        nodes: group.length + 1
      })));

    The comments I think are self explanatory. This is just grouping up the "nodes" by a common root node. Then I just take out the length of those groups. The Map structures certainly does hide some of the operation complexity though.

    Edit: Just realized, you wanted the node count of the largest tree. At this point, I would call this a formatting issue since you already have your nodes grouped:

    function largestTreeCount(nodes){
      let groups = groupByRootNode(nodes);
      let totalNodes = Array.from(groups, ([r, group]) => group.length+1);
      return Math.max(...totalNodes);
    }
    
    Reply
  3. Slightly puzzled because it is most common for a Tree data structure to simply record how many nodes are currently in them, incrementing and decrementing the count as necessary. (Trees often harbor other kinds of so-called "statistics.")

    Reply
  4. You could build a tree with all nodes as reference in an object, get heads and count nested tries. Finally get the maximum value.

    const
        pairs = [[1, 3], [1, 4], [3, 5], [4, 6], [7, 8]],
        heads = new Set(pairs.map(([n]) => n)),
        references = {},
        count = nodes => nodes.reduce((s, n) => s + 1 + count(Object.keys(references[n])), 0);
    
    pairs.forEach(([parent, child]) => {
        heads.delete(child);
        references[parent] ??= { };
        references[parent][child] = references[child] ??= { };
    });
    
    console.log(Math.max(...[...heads].map(n => count([n]))));
    console.log(references);
    .as-console-wrapper { max-height: 100% !important; top: 0; }
    Reply

Leave a Comment