Removing nodes from a tree properly

Question

I have the following function that prunes a tree data structure :

public static void pruneTree(final ConditionTreeNode treeNode) {

    final List<ConditionTreeNode> subTrees = treeNode.getSubTrees();

    for (ConditionTreeNode current : subTrees) {
        pruneTree(current);
    }

    if(subTrees.isEmpty()) {
        final ConditionTreeNode parent = treeNode.getParent();
        parent.removeConditionTreeNode(treeNode);
    }

    if (treeNode.isLeaf()) {
        //this is the base case
        if (treeNode.isPrunable()) {
            final ConditionTreeNode parent = treeNode.getParent();
            parent.removeConditionTreeNode(treeNode);
        }
        return;
    }

}

and I want to know what the best way to prune this is. I'm getting ConcurrentModificationExceptions currently, and I've read that you can copy the collection, and remove the original -- or remove from an iterator. Can someone help me understand what I need to do inorder for this method to work?

Answer 1

The problem is, you are iterating through the collection of nodes and in some cases removing the actual item from the collection inside the recursive call. You could instead return a boolean flag from the recursive call to sign that the actual item is to be removed, then remove it via Iterator.remove() (you need to change the foreach loop to an iterator loop to make this possible).

Replacing the actual item with its only subnode is trickier - you could define a custom class to return more info from the recursive method call, but it starts to become awkward. Or you may consider replacing the recursive call with a loop using e.g. a stack.