Find root of largest tree

Today we will discuss a popular interview question. The problem tests a developers hands-on on various aspect of Java programming language as well as his problem solving ability. The resultant solution must have optimum time and space complexity.

Problem Statement:

Find the root of largest tree in the forest. Given each tree is represented as a hashmap entry with child as the key and parent as the value. Higher the number of children for any given root larger the tree.

constrains:

a. One child has only one immediate parent

b. Any parent can have more than one children

c. If two trees are equal then return root with least id

Sample forest: {{1 -> 2}{3 -> 4}}

Here we have 2 trees, one with node 1 and root 2 and second with node 3 and root 4. Both trees have same size hence the output should be the node with least id ie. 2.

Solution: 

Approach: We receive input hashmap with key as child and value as parent, hence child nodes are unique in this collection but parent values can be duplicate for more than one keys. Here we don't get a view of how many children . Hence we need to maintain a different map where the parent will be key and number of children will be its value.

However even after doing this we will not know exactly how many trees are present in our forest. Number of trees in our forest equals number of root nodes. Root nodes are nodes which do not have a parent. Thus we can recursively check in the input hashmap if the parent of current element is also present in the map as key. This means our parent also has a parent. In this case we need to add that parent to our parent map and increment the count of its children as well.

For sample input as {{1->2}{3->4}{4->5}{6->2}}

The parent map will look like { 2-2, 4-2, 5-3 }

Now we just need to extract the entry with largest value from parent map.

The list of largest trees will look like {2,5}

 If there are more than one entries with highest number of children than we extract the least id and return that root. Stream API in Java 8 can achieve this easily.

import java.util.*;


public class Forest {

   
    HashMap<Integer,Integer> trees;   
    public int getLargestTree(HashMap<Integer,Integer> trees){
        this.trees = trees;
        //construct parent map
        Map<Integer,Integer> parentMap = createParentMap(trees);
    
        //get largest trees
        List<Integer> largestTrees = getLargestTrees(parentMap);
    
        //get min id and return
        return largestTrees.stream().mapToInt(v->v).min().orElse(Integer.MAX_VALUE);

    }
    
    private Map<Integer,Integer> createParentMap(HashMap<Integer,Integer> trees){
        Map<Integer,Integer> parentMap = new HashMap<>();
        for(Map.Entry<Integer,Integer> e : trees.entrySet()){
            int parent = e.getValue();
            int value=parentMap.containsKey(parent)?parentMap.get(parent)+1:1;
            parentMap.put(parent,value);
            incrementChildCountForParent(parent,parentMap);
        }
        return parentMap;
    }
    
    private List<Integer> getLargestTrees(Map<Integer,Integer> parentMap){
        int maxChildren = 0;
        List<Integer> largestTrees = new ArrayList<>();
        for(Map.Entry<Integer,Integer> e : parentMap.entrySet()){
            if(e.getValue()>maxChildren){
                maxChildren = e.getValue();
                largestTrees.clear();
                largestTrees.add(e.getKey());
            }
            else if(e.getValue()==maxChildren){
                largestTrees.add(e.getKey());
            }
        }
        return largestTrees;
    }

    public void incrementChildCountForParent(int child, Map<Integer,Integer> parentMap) {
        
        if(trees.get(child)==null) return;
        
        int parent = trees.get(child);
        int value= parentMap.containsKey(parent)?parentMap.get(parent)+1:1;   
    
        parentMap.put(parent,value);
        
        incrementChildCountForParent(parent, parentMap);
    }
    
    public static void main(String args[]) {
      HashMap<Integer,Integer> forest = new HashMap<>();
      forest.put(1,2);
      forest.put(3,4);
      forest.put(4,5);
      forest.put(6,2);
      forest.put(7,4);
      System.out.println("Root of largest tree is "+new Forest().getLargestTree(forest));
      
    }
}


The time and space complexity of above program is O(n). This is because the time and space required varies as per the size of the input hashmap and the number of root nodes contained in it.

Is it possible to optimize this solution any further, currently I do not think so. However you can let me know your thoughts in the comments. Would love to see a insightful conversion.