avoid java.util.ConcurrentModificationException using ArrayList and recursion

Question

I'm trying to construct binary tree from given edges and root. I iterate over all lines and set left child to given node(and right child if second occurrence of given node is found). And when child node is set I remove this element from ArrayList and call function recursively on child.

List<Integer[]> edges = new ArrayList<>();

This array list is e.g:

3 4
3 0
4 5
1 3
2 4 

and root is 1. I have class Node

public class Node {
public Node left;
public Node right;
public int key;

public Node(int k) {
    key = k;
    left = null;
    right = null;
}
...}

And my function to construct a tree is:

public static void edgeToNodes(Node root) {
    if (root == null) return;
    int count = 0;

    for (Iterator<Integer[]> iterator = edges.iterator(); iterator.hasNext(); ) {
        Integer[] edge = iterator.next();
        for (int i = 0; i < edge.length; i++) {
            if (edge[i] == root.key) {
                if (count == 0) {
                    Node left;
                    if (i == 0) {
                        left = new Node(edge[1]);
                        root.setLeft(left);
                    } else {
                        left = new Node(edge[0]);
                        root.setLeft(left);
                    }

                    iterator.remove();
                    count++;
                    edgeToNodes(left);
                } else {
                    Node right;
                    if (i == 0) {
                        right = new Node(edge[1]);
                        root.setRight(right);
                    } else {
                        right = new Node(edge[0]);
                        root.setRight(right);
                    }

                    iterator.remove();
                    edgeToNodes(right);
                }
            }
        }
    }
}

Problem is that it gives me java.util.ConcurrentModificationException on line Integer[] edge = iterator.next(); and edgeToNodes(left); How can I avoid this exception?

Answer 1

You are removing elements from the list while iterating on it.

It would work if you did it with via only one iterator. The problem is that you use recursion and therefore create several iterators which modify the same list. This causes the ConcurrentModificationException.

You could build the nodes in a more iterative way.

• Start from the root node.
• Maintain a list of nodes to visit (lets call it pendingNodes).
• Initialize it with the root node.
• While the list of pending nodes is not empty :
  • Take the first element of pendingNodes.
  • Find its potential children.
  • If there are some children nodes that are not already visited
    • Link them to the parent node.
    • Add them to the list of pendingNodes.

Here is an example of code :

public class Problem {

  private List<Integer[]> edges;
  private LinkedList<Node> pendingNodes = new LinkedList<>();
  private Map<Integer, Node> nodeMap = new HashMap<>();
  private Set<Integer> visitedNodes = new HashSet<>();

  public Problem(List<Integer[]> edges) {
    this.edges = edges;
  }

  public void run(Integer root) {
    //Initialization
    Node rootNode = new Node(root);
    this.pendingNodes.add(rootNode);
    this.nodeMap.put(root, rootNode);

    while(!pendingNodes.isEmpty()) {
      Node parent = pendingNodes.poll();
      for (Integer[] edge : edges) {
        if(edge[0].equals(parent.getKey())) {
          link(parent, edge[1]);
        } else if (edge[1].equals(parent.getKey())) {
          link(parent, edge[0]);
        }
      }
      visitedNodes.add(parent.getKey());
    }
  }

  public void link(Node parent, Integer child) {
    if(!visitedNodes.contains(child)) {
      //get the corresponding node, create it if not exists
      Node childNode = nodeMap.get(child);
      if (childNode == null) {
        childNode = new Node(child);
        nodeMap.put(child, childNode);
        pendingNodes.add(childNode);
      }

      //Choose between left and right...
      if (parent.getLeft() == null) {
        parent.setLeft(childNode);
      } else {
        parent.setRight(childNode);
      }
    }
  }

  public static void main(String[] args) {

    //Build the input dataset
    List<Integer[]> edges = Arrays.asList(
        new Integer[]{3, 4},
        new Integer[]{3, 0},
        new Integer[]{4, 5},
        new Integer[]{1, 3},
        new Integer[]{2, 4}
    );

    Problem problem = new Problem(edges);
    problem.run(1);

    Map<Integer, Node> nodeMap = problem.nodeMap;
    for (Node node : nodeMap.values()) {
      System.out.println(node);
    }
  }

}

Output (I customized Node#toString()):

0 => {null, null}
1 => {3, null}
2 => {null, null}
3 => {4, 0}
4 => {5, 2}
5 => {null, null}

Answer 2

The problem you have is that each time you do a recursion, you create a new iterator over the same list. That iterator (at some point) then removes items from that list and you go back up in your recursion. However back up one step your list just lost an element WHILE you were iterating over it without it being removed by the iterator itself (it was removed by the iterator one step further down the recursion line).

=> ConcurrentModificationException