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:

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?

I'm having a hard time envisioning what the resulting tree is supposed to look like. What do you expect your output to be? — Ian McLaird
– Ian McLaird, Commented Mar 17, 2016 at 13:54
@IanMcLaird Then I traverse tree inorder and in this example I expect: 5 4 2 3 0 1 — user2950602
– user2950602, Commented Mar 17, 2016 at 14:04

Arnaud Denoyelle · Accepted Answer · 2016-03-17 18:07:45Z

2

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}

edited Mar 17, 2016 at 18:07

answered Mar 17, 2016 at 13:42

Arnaud Denoyelle

31.5k18 gold badges106 silver badges161 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

user2950602 Over a year ago

I didn't quite understand what happens here: node.setLeft(node);

user2950602 Over a year ago

in my task edge[0] or edge[1] can be parent

Arnaud Denoyelle Over a year ago

@user2950602 So how do you choose which one is the parent?

user2950602 Over a year ago

I tried to go through list, find root, choose another element on that edge as child, recursively do the same with child

Arnaud Denoyelle Over a year ago

@user2950602 Then it is like walking through a graph. I edited the answer.

Mark · Accepted Answer · 2016-03-17 13:42:44Z

1

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

answered Mar 17, 2016 at 13:42

Mark

1,4981 gold badge9 silver badges13 bronze badges

1 Comment

IgorGanapolsky Over a year ago

What solution is proposed?

Collectives™ on Stack Overflow

avoid java.util.ConcurrentModificationException using ArrayList and recursion

2 Answers 2

5 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related