I'm trying to understand why some of my code doesn't throw a ConcurrentModificationException. I am looping through elements of a Set and then adding more elements to the set, but I expected an exception.
Problem: Given a directed tree, return true if two given nodes have a common ancestor. Note this is not a rooted tree (i.e. a tree with one root). We are given edge pairs that are (parent, child). Nodes have unique IDs.
import java.io.*;
import java.util.*;
class Solution {
public static void main(String[] args) {
int[][] pairs = {{11,6},{9,6},{9,8},{10,8}, {6,2},{5,2},{5,1},{8,3},{8,4}};
System.out.println(hasCommonAncestor(pairs, 3,4));
System.out.println(hasCommonAncestor(pairs, 2,4));
System.out.println(hasCommonAncestor(pairs, 1,3));
System.out.println(hasCommonAncestor(pairs, 6,8));
}
private static boolean hasCommonAncestor(int[][] pairs, int a, int b) {
Map<Integer, Set<Integer>> firstLevelParents = new HashMap<>();
for(int[] pair : pairs) {
int parent = pair[0];
int child = pair[1];
Set<Integer> parents = firstLevelParents.getOrDefault(child, new HashSet<>());
parents.add(parent);
firstLevelParents.put(child, parents);
}
Set<Integer> aParents = firstLevelParents.get(a);
Set<Integer> bParents = firstLevelParents.get(b);
for(Integer parent : aParents) {
Set<Integer> parentsParents = firstLevelParents.getOrDefault(parent, new HashSet<>());
aParents.addAll(parentsParents);
}
for(Integer parent : bParents) {
Set<Integer> parentsParents = firstLevelParents.getOrDefault(parent, new HashSet<>());
bParents.addAll(parentsParents);
}
return aParents.removeAll(bParents);
}
}